This repository was archived by the owner on Jul 11, 2025. It is now read-only.
forked from phoboslab/JavaScriptCore-iOS
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMarkedBlock.h
More file actions
483 lines (384 loc) · 14 KB
/
MarkedBlock.h
File metadata and controls
483 lines (384 loc) · 14 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
/*
* Copyright (C) 1999-2000 Harri Porten ([email protected])
* Copyright (C) 2001 Peter Kelly ([email protected])
* Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2011 Apple Inc. All rights reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
*/
#ifndef MarkedBlock_h
#define MarkedBlock_h
#include "BlockAllocator.h"
#include "HeapBlock.h"
#include "WeakSet.h"
#include <wtf/Bitmap.h>
#include <wtf/DataLog.h>
#include <wtf/DoublyLinkedList.h>
#include <wtf/HashFunctions.h>
#include <wtf/PageAllocationAligned.h>
#include <wtf/StdLibExtras.h>
#include <wtf/Vector.h>
// Set to log state transitions of blocks.
#define HEAP_LOG_BLOCK_STATE_TRANSITIONS 0
#if HEAP_LOG_BLOCK_STATE_TRANSITIONS
#define HEAP_LOG_BLOCK_STATE_TRANSITION(block) do { \
dataLogF( \
"%s:%d %s: block %s = %p, %d\n", \
__FILE__, __LINE__, __FUNCTION__, \
#block, (block), (block)->m_state); \
} while (false)
#else
#define HEAP_LOG_BLOCK_STATE_TRANSITION(block) ((void)0)
#endif
namespace JSC {
class Heap;
class JSCell;
class MarkedAllocator;
typedef uintptr_t Bits;
static const size_t MB = 1024 * 1024;
bool isZapped(const JSCell*);
// A marked block is a page-aligned container for heap-allocated objects.
// Objects are allocated within cells of the marked block. For a given
// marked block, all cells have the same size. Objects smaller than the
// cell size may be allocated in the marked block, in which case the
// allocation suffers from internal fragmentation: wasted space whose
// size is equal to the difference between the cell size and the object
// size.
class MarkedBlock : public HeapBlock<MarkedBlock> {
friend class LLIntOffsetsExtractor;
public:
static const size_t atomSize = 8; // bytes
static const size_t atomShiftAmount = 4; // log_2(atomSize) FIXME: Change atomSize to 16.
static const size_t blockSize = 64 * KB;
static const size_t blockMask = ~(blockSize - 1); // blockSize must be a power of two.
static const size_t atomsPerBlock = blockSize / atomSize;
static const size_t atomMask = atomsPerBlock - 1;
static const size_t markByteShiftAmount = 3; // log_2(word size for m_marks) FIXME: Change word size for m_marks to uint8_t.
struct FreeCell {
FreeCell* next;
};
struct FreeList {
FreeCell* head;
size_t bytes;
FreeList();
FreeList(FreeCell*, size_t);
};
struct VoidFunctor {
typedef void ReturnType;
void returnValue() { }
};
class CountFunctor {
public:
typedef size_t ReturnType;
CountFunctor() : m_count(0) { }
void count(size_t count) { m_count += count; }
ReturnType returnValue() { return m_count; }
private:
ReturnType m_count;
};
enum DestructorType { None, ImmortalStructure, Normal };
static MarkedBlock* create(DeadBlock*, MarkedAllocator*, size_t cellSize, DestructorType);
static bool isAtomAligned(const void*);
static MarkedBlock* blockFor(const void*);
static size_t firstAtom();
void lastChanceToFinalize();
MarkedAllocator* allocator() const;
Heap* heap() const;
VM* vm() const;
WeakSet& weakSet();
enum SweepMode { SweepOnly, SweepToFreeList };
FreeList sweep(SweepMode = SweepOnly);
void shrink();
void visitWeakSet(HeapRootVisitor&);
void reapWeakSet();
// While allocating from a free list, MarkedBlock temporarily has bogus
// cell liveness data. To restore accurate cell liveness data, call one
// of these functions:
void didConsumeFreeList(); // Call this once you've allocated all the items in the free list.
void stopAllocating(const FreeList&);
FreeList resumeAllocating(); // Call this if you canonicalized a block for some non-collection related purpose.
void didConsumeEmptyFreeList(); // Call this if you sweep a block, but the returned FreeList is empty.
// Returns true if the "newly allocated" bitmap was non-null
// and was successfully cleared and false otherwise.
bool clearNewlyAllocated();
void clearMarks();
size_t markCount();
bool isEmpty();
size_t cellSize();
DestructorType destructorType();
size_t size();
size_t capacity();
bool isMarked(const void*);
bool testAndSetMarked(const void*);
bool isLive(const JSCell*);
bool isLiveCell(const void*);
void setMarked(const void*);
void clearMarked(const void*);
bool isNewlyAllocated(const void*);
void setNewlyAllocated(const void*);
void clearNewlyAllocated(const void*);
bool needsSweeping();
template <typename Functor> void forEachCell(Functor&);
template <typename Functor> void forEachLiveCell(Functor&);
template <typename Functor> void forEachDeadCell(Functor&);
static ptrdiff_t offsetOfMarks() { return OBJECT_OFFSETOF(MarkedBlock, m_marks); }
private:
static const size_t atomAlignmentMask = atomSize - 1; // atomSize must be a power of two.
enum BlockState { New, FreeListed, Allocated, Marked };
template<DestructorType> FreeList sweepHelper(SweepMode = SweepOnly);
typedef char Atom[atomSize];
MarkedBlock(Region*, MarkedAllocator*, size_t cellSize, DestructorType);
Atom* atoms();
size_t atomNumber(const void*);
void callDestructor(JSCell*);
template<BlockState, SweepMode, DestructorType> FreeList specializedSweep();
size_t m_atomsPerCell;
size_t m_endAtom; // This is a fuzzy end. Always test for < m_endAtom.
#if ENABLE(PARALLEL_GC)
WTF::Bitmap<atomsPerBlock, WTF::BitmapAtomic> m_marks;
#else
WTF::Bitmap<atomsPerBlock, WTF::BitmapNotAtomic> m_marks;
#endif
OwnPtr<WTF::Bitmap<atomsPerBlock>> m_newlyAllocated;
DestructorType m_destructorType;
MarkedAllocator* m_allocator;
BlockState m_state;
WeakSet m_weakSet;
};
inline MarkedBlock::FreeList::FreeList()
: head(0)
, bytes(0)
{
}
inline MarkedBlock::FreeList::FreeList(FreeCell* head, size_t bytes)
: head(head)
, bytes(bytes)
{
}
inline size_t MarkedBlock::firstAtom()
{
return WTF::roundUpToMultipleOf<atomSize>(sizeof(MarkedBlock)) / atomSize;
}
inline MarkedBlock::Atom* MarkedBlock::atoms()
{
return reinterpret_cast<Atom*>(this);
}
inline bool MarkedBlock::isAtomAligned(const void* p)
{
return !(reinterpret_cast<Bits>(p) & atomAlignmentMask);
}
inline MarkedBlock* MarkedBlock::blockFor(const void* p)
{
return reinterpret_cast<MarkedBlock*>(reinterpret_cast<Bits>(p) & blockMask);
}
inline void MarkedBlock::lastChanceToFinalize()
{
m_weakSet.lastChanceToFinalize();
clearNewlyAllocated();
clearMarks();
sweep();
}
inline MarkedAllocator* MarkedBlock::allocator() const
{
return m_allocator;
}
inline Heap* MarkedBlock::heap() const
{
return m_weakSet.heap();
}
inline VM* MarkedBlock::vm() const
{
return m_weakSet.vm();
}
inline WeakSet& MarkedBlock::weakSet()
{
return m_weakSet;
}
inline void MarkedBlock::shrink()
{
m_weakSet.shrink();
}
inline void MarkedBlock::visitWeakSet(HeapRootVisitor& heapRootVisitor)
{
m_weakSet.visit(heapRootVisitor);
}
inline void MarkedBlock::reapWeakSet()
{
m_weakSet.reap();
}
inline void MarkedBlock::didConsumeFreeList()
{
HEAP_LOG_BLOCK_STATE_TRANSITION(this);
ASSERT(m_state == FreeListed);
m_state = Allocated;
}
inline void MarkedBlock::didConsumeEmptyFreeList()
{
HEAP_LOG_BLOCK_STATE_TRANSITION(this);
ASSERT(!m_newlyAllocated);
#ifndef NDEBUG
for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell)
ASSERT(m_marks.get(i));
#endif
ASSERT(m_state == FreeListed);
m_state = Marked;
}
inline void MarkedBlock::clearMarks()
{
HEAP_LOG_BLOCK_STATE_TRANSITION(this);
ASSERT(m_state != New && m_state != FreeListed);
m_marks.clearAll();
// This will become true at the end of the mark phase. We set it now to
// avoid an extra pass to do so later.
m_state = Marked;
}
inline size_t MarkedBlock::markCount()
{
return m_marks.count();
}
inline bool MarkedBlock::isEmpty()
{
return m_marks.isEmpty() && m_weakSet.isEmpty() && (!m_newlyAllocated || m_newlyAllocated->isEmpty());
}
inline size_t MarkedBlock::cellSize()
{
return m_atomsPerCell * atomSize;
}
inline MarkedBlock::DestructorType MarkedBlock::destructorType()
{
return m_destructorType;
}
inline size_t MarkedBlock::size()
{
return markCount() * cellSize();
}
inline size_t MarkedBlock::capacity()
{
return region()->blockSize();
}
inline size_t MarkedBlock::atomNumber(const void* p)
{
return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
}
inline bool MarkedBlock::isMarked(const void* p)
{
return m_marks.get(atomNumber(p));
}
inline bool MarkedBlock::testAndSetMarked(const void* p)
{
return m_marks.concurrentTestAndSet(atomNumber(p));
}
inline void MarkedBlock::setMarked(const void* p)
{
m_marks.set(atomNumber(p));
}
inline void MarkedBlock::clearMarked(const void* p)
{
ASSERT(m_marks.get(atomNumber(p)));
m_marks.clear(atomNumber(p));
}
inline bool MarkedBlock::isNewlyAllocated(const void* p)
{
return m_newlyAllocated->get(atomNumber(p));
}
inline void MarkedBlock::setNewlyAllocated(const void* p)
{
m_newlyAllocated->set(atomNumber(p));
}
inline void MarkedBlock::clearNewlyAllocated(const void* p)
{
m_newlyAllocated->clear(atomNumber(p));
}
inline bool MarkedBlock::clearNewlyAllocated()
{
if (m_newlyAllocated) {
m_newlyAllocated.clear();
return true;
}
return false;
}
inline bool MarkedBlock::isLive(const JSCell* cell)
{
switch (m_state) {
case Allocated:
return true;
case Marked:
return m_marks.get(atomNumber(cell)) || (m_newlyAllocated && isNewlyAllocated(cell));
case New:
case FreeListed:
RELEASE_ASSERT_NOT_REACHED();
return false;
}
RELEASE_ASSERT_NOT_REACHED();
return false;
}
inline bool MarkedBlock::isLiveCell(const void* p)
{
ASSERT(MarkedBlock::isAtomAligned(p));
size_t atomNumber = this->atomNumber(p);
size_t firstAtom = this->firstAtom();
if (atomNumber < firstAtom) // Filters pointers into MarkedBlock metadata.
return false;
if ((atomNumber - firstAtom) % m_atomsPerCell) // Filters pointers into cell middles.
return false;
if (atomNumber >= m_endAtom) // Filters pointers into invalid cells out of the range.
return false;
return isLive(static_cast<const JSCell*>(p));
}
template <typename Functor> inline void MarkedBlock::forEachCell(Functor& functor)
{
for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
JSCell* cell = reinterpret_cast_ptr<JSCell*>(&atoms()[i]);
functor(cell);
}
}
template <typename Functor> inline void MarkedBlock::forEachLiveCell(Functor& functor)
{
for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
JSCell* cell = reinterpret_cast_ptr<JSCell*>(&atoms()[i]);
if (!isLive(cell))
continue;
functor(cell);
}
}
template <typename Functor> inline void MarkedBlock::forEachDeadCell(Functor& functor)
{
for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
JSCell* cell = reinterpret_cast_ptr<JSCell*>(&atoms()[i]);
if (isLive(cell))
continue;
functor(cell);
}
}
inline bool MarkedBlock::needsSweeping()
{
return m_state == Marked;
}
} // namespace JSC
namespace WTF {
struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
static unsigned hash(JSC::MarkedBlock* const& key)
{
// Aligned VM regions tend to be monotonically increasing integers,
// which is a great hash function, but we have to remove the low bits,
// since they're always zero, which is a terrible hash function!
return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
}
};
template<> struct DefaultHash<JSC::MarkedBlock*> {
typedef MarkedBlockHash Hash;
};
} // namespace WTF
#endif // MarkedBlock_h