Bmalloc and GC should put auxiliaries (butterflies, typed array backing stores) in...
[WebKit.git] / Source / JavaScriptCore / heap / MarkedBlock.h
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2001 Peter Kelly (pmk@post.com)
4  *  Copyright (C) 2003-2017 Apple Inc. All rights reserved.
5  *
6  *  This library is free software; you can redistribute it and/or
7  *  modify it under the terms of the GNU Lesser General Public
8  *  License as published by the Free Software Foundation; either
9  *  version 2 of the License, or (at your option) any later version.
10  *
11  *  This library is distributed in the hope that it will be useful,
12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  *  Lesser General Public License for more details.
15  *
16  *  You should have received a copy of the GNU Lesser General Public
17  *  License along with this library; if not, write to the Free Software
18  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
19  *
20  */
21
22 #pragma once
23
24 #include "AllocatorAttributes.h"
25 #include "DestructionMode.h"
26 #include "HeapCell.h"
27 #include "IterationStatus.h"
28 #include "WeakSet.h"
29 #include <wtf/Atomics.h>
30 #include <wtf/Bitmap.h>
31 #include <wtf/HashFunctions.h>
32 #include <wtf/StdLibExtras.h>
33
34 namespace JSC {
35     
36 class FreeList;
37 class Heap;
38 class JSCell;
39 class MarkedAllocator;
40 class MarkedSpace;
41 class SlotVisitor;
42 class Subspace;
43
44 typedef uintptr_t Bits;
45 typedef uint32_t HeapVersion;
46
47 // A marked block is a page-aligned container for heap-allocated objects.
48 // Objects are allocated within cells of the marked block. For a given
49 // marked block, all cells have the same size. Objects smaller than the
50 // cell size may be allocated in the marked block, in which case the
51 // allocation suffers from internal fragmentation: wasted space whose
52 // size is equal to the difference between the cell size and the object
53 // size.
54
55 class MarkedBlock {
56     WTF_MAKE_NONCOPYABLE(MarkedBlock);
57     friend class LLIntOffsetsExtractor;
58     friend struct VerifyMarked;
59
60 public:
61     class Handle;
62 private:
63     friend class Handle;
64 public:
65     static const size_t atomSize = 16; // bytes
66     static const size_t blockSize = 16 * KB;
67     static const size_t blockMask = ~(blockSize - 1); // blockSize must be a power of two.
68
69     static const size_t atomsPerBlock = blockSize / atomSize;
70
71     static_assert(!(MarkedBlock::atomSize & (MarkedBlock::atomSize - 1)), "MarkedBlock::atomSize must be a power of two.");
72     static_assert(!(MarkedBlock::blockSize & (MarkedBlock::blockSize - 1)), "MarkedBlock::blockSize must be a power of two.");
73     
74     struct VoidFunctor {
75         typedef void ReturnType;
76         void returnValue() { }
77     };
78     
79     class CountFunctor {
80     public:
81         typedef size_t ReturnType;
82
83         CountFunctor() : m_count(0) { }
84         void count(size_t count) const { m_count += count; }
85         ReturnType returnValue() const { return m_count; }
86
87     private:
88         // FIXME: This is mutable because we're using a functor rather than C++ lambdas.
89         // https://bugs.webkit.org/show_bug.cgi?id=159644
90         mutable ReturnType m_count;
91     };
92         
93     class Handle {
94         WTF_MAKE_NONCOPYABLE(Handle);
95         WTF_MAKE_FAST_ALLOCATED;
96         friend class LLIntOffsetsExtractor;
97         friend class MarkedBlock;
98         friend struct VerifyMarked;
99     public:
100             
101         ~Handle();
102             
103         MarkedBlock& block();
104             
105         void* cellAlign(void*);
106             
107         bool isEmpty();
108
109         void lastChanceToFinalize();
110
111         MarkedAllocator* allocator() const;
112         Subspace* subspace() const;
113         Heap* heap() const;
114         inline MarkedSpace* space() const;
115         VM* vm() const;
116         WeakSet& weakSet();
117             
118         enum SweepMode { SweepOnly, SweepToFreeList };
119
120         // Sweeping ensures that destructors get called and removes the block from the unswept
121         // set. Sweeping to free list also removes the block from the empty set, if it was in that
122         // set. Sweeping with SweepOnly may add this block to the empty set, if the block is found
123         // to be empty. The free-list being null implies SweepOnly.
124         //
125         // Note that you need to make sure that the empty bit reflects reality. If it's not set
126         // and the block is freshly created, then we'll make the mistake of running destructors in
127         // the block. If it's not set and the block has nothing marked, then we'll make the
128         // mistake of making a pop freelist rather than a bump freelist.
129         void sweep(FreeList*);
130         
131         // This is to be called by Subspace.
132         template<typename DestroyFunc>
133         void finishSweepKnowingSubspace(FreeList*, const DestroyFunc&);
134         
135         void unsweepWithNoNewlyAllocated();
136         
137         void zap(const FreeList&);
138         
139         void shrink();
140             
141         void visitWeakSet(SlotVisitor&);
142         void reapWeakSet();
143             
144         // While allocating from a free list, MarkedBlock temporarily has bogus
145         // cell liveness data. To restore accurate cell liveness data, call one
146         // of these functions:
147         void didConsumeFreeList(); // Call this once you've allocated all the items in the free list.
148         void stopAllocating(const FreeList&);
149         void resumeAllocating(FreeList&); // Call this if you canonicalized a block for some non-collection related purpose.
150             
151         size_t cellSize();
152         inline unsigned cellsPerBlock();
153         
154         const AllocatorAttributes& attributes() const;
155         DestructionMode destruction() const;
156         bool needsDestruction() const;
157         HeapCell::Kind cellKind() const;
158             
159         size_t markCount();
160         size_t size();
161         
162         inline bool isLive(HeapVersion markingVersion, bool isMarking, const HeapCell*);
163         inline bool isLiveCell(HeapVersion markingVersion, bool isMarking, const void*);
164
165         bool isLive(const HeapCell*);
166         bool isLiveCell(const void*);
167
168         bool isFreeListedCell(const void* target) const;
169
170         bool isNewlyAllocated(const void*);
171         void setNewlyAllocated(const void*);
172         void clearNewlyAllocated(const void*);
173         
174         HeapVersion newlyAllocatedVersion() const { return m_newlyAllocatedVersion; }
175         
176         inline bool isNewlyAllocatedStale() const;
177         
178         inline bool hasAnyNewlyAllocated();
179         void resetAllocated();
180         
181         template <typename Functor> IterationStatus forEachCell(const Functor&);
182         template <typename Functor> inline IterationStatus forEachLiveCell(const Functor&);
183         template <typename Functor> inline IterationStatus forEachDeadCell(const Functor&);
184         template <typename Functor> inline IterationStatus forEachMarkedCell(const Functor&);
185             
186         JS_EXPORT_PRIVATE bool areMarksStale();
187         
188         void assertMarksNotStale();
189             
190         bool isFreeListed() const { return m_isFreeListed; }
191         
192         size_t index() const { return m_index; }
193         
194         void removeFromAllocator();
195         
196         void didAddToAllocator(MarkedAllocator*, size_t index);
197         void didRemoveFromAllocator();
198         
199         void dumpState(PrintStream&);
200         
201     private:
202         Handle(Heap&, Subspace*, void*);
203         
204         enum SweepDestructionMode { BlockHasNoDestructors, BlockHasDestructors, BlockHasDestructorsAndCollectorIsRunning };
205         enum ScribbleMode { DontScribble, Scribble };
206         enum EmptyMode { IsEmpty, NotEmpty };
207         enum NewlyAllocatedMode { HasNewlyAllocated, DoesNotHaveNewlyAllocated };
208         enum MarksMode { MarksStale, MarksNotStale };
209         
210         SweepDestructionMode sweepDestructionMode();
211         EmptyMode emptyMode();
212         ScribbleMode scribbleMode();
213         NewlyAllocatedMode newlyAllocatedMode();
214         MarksMode marksMode();
215         
216         template<bool, EmptyMode, SweepMode, SweepDestructionMode, ScribbleMode, NewlyAllocatedMode, MarksMode, typename DestroyFunc>
217         void specializedSweep(FreeList*, EmptyMode, SweepMode, SweepDestructionMode, ScribbleMode, NewlyAllocatedMode, MarksMode, const DestroyFunc&);
218         
219         void setIsFreeListed();
220         
221         MarkedBlock::Handle* m_prev { nullptr };
222         MarkedBlock::Handle* m_next { nullptr };
223             
224         size_t m_atomsPerCell { std::numeric_limits<size_t>::max() };
225         size_t m_endAtom { std::numeric_limits<size_t>::max() }; // This is a fuzzy end. Always test for < m_endAtom.
226             
227         WTF::Bitmap<atomsPerBlock> m_newlyAllocated;
228             
229         AllocatorAttributes m_attributes;
230         bool m_isFreeListed { false };
231
232         Subspace* m_subspace { nullptr };
233         MarkedAllocator* m_allocator { nullptr };
234         size_t m_index { std::numeric_limits<size_t>::max() };
235         WeakSet m_weakSet;
236         
237         HeapVersion m_newlyAllocatedVersion;
238             
239         MarkedBlock* m_block { nullptr };
240     };
241         
242     static MarkedBlock::Handle* tryCreate(Heap&, Subspace*);
243         
244     Handle& handle();
245         
246     VM* vm() const;
247     inline Heap* heap() const;
248     inline MarkedSpace* space() const;
249
250     static bool isAtomAligned(const void*);
251     static MarkedBlock* blockFor(const void*);
252     static size_t firstAtom();
253     size_t atomNumber(const void*);
254         
255     size_t markCount();
256
257     bool isMarked(const void*);
258     bool isMarked(HeapVersion markingVersion, const void*);
259     bool isMarkedConcurrently(HeapVersion markingVersion, const void*);
260     bool isMarked(const void*, Dependency);
261     bool testAndSetMarked(const void*, Dependency);
262         
263     bool isAtom(const void*);
264     void clearMarked(const void*);
265     
266     size_t cellSize();
267     const AllocatorAttributes& attributes() const;
268     
269     bool hasAnyMarked() const;
270     void noteMarked();
271 #if ASSERT_DISABLED
272     void assertValidCell(VM&, HeapCell*) const { }
273 #else
274     void assertValidCell(VM&, HeapCell*) const;
275 #endif
276         
277     WeakSet& weakSet();
278
279     JS_EXPORT_PRIVATE bool areMarksStale();
280     bool areMarksStale(HeapVersion markingVersion);
281     DependencyWith<bool> areMarksStaleWithDependency(HeapVersion markingVersion);
282     
283     Dependency aboutToMark(HeapVersion markingVersion);
284         
285 #if ASSERT_DISABLED
286     void assertMarksNotStale() { }
287 #else
288     JS_EXPORT_PRIVATE void assertMarksNotStale();
289 #endif
290         
291     bool needsDestruction() const { return m_needsDestruction; }
292     
293     // This is usually a no-op, and we use it as a no-op that touches the page in isPagedOut().
294     void updateNeedsDestruction();
295     
296     void resetMarks();
297     
298     bool isMarkedRaw(const void* p);
299     HeapVersion markingVersion() const { return m_markingVersion; }
300
301 private:
302     static const size_t atomAlignmentMask = atomSize - 1;
303
304     typedef char Atom[atomSize];
305
306     MarkedBlock(VM&, Handle&);
307     Atom* atoms();
308         
309     JS_EXPORT_PRIVATE void aboutToMarkSlow(HeapVersion markingVersion);
310     void clearHasAnyMarked();
311     
312     void noteMarkedSlow();
313     
314     inline bool marksConveyLivenessDuringMarking(HeapVersion markingVersion);
315         
316     WTF::Bitmap<atomsPerBlock> m_marks;
317
318     bool m_needsDestruction;
319     Lock m_lock;
320     
321     // The actual mark count can be computed by doing: m_biasedMarkCount - m_markCountBias. Note
322     // that this count is racy. It will accurately detect whether or not exactly zero things were
323     // marked, but if N things got marked, then this may report anything in the range [1, N] (or
324     // before unbiased, it would be [1 + m_markCountBias, N + m_markCountBias].)
325     int16_t m_biasedMarkCount;
326     
327     // We bias the mark count so that if m_biasedMarkCount >= 0 then the block should be retired.
328     // We go to all this trouble to make marking a bit faster: this way, marking knows when to
329     // retire a block using a js/jns on m_biasedMarkCount.
330     //
331     // For example, if a block has room for 100 objects and retirement happens whenever 90% are
332     // live, then m_markCountBias will be -90. This way, when marking begins, this will cause us to
333     // set m_biasedMarkCount to -90 as well, since:
334     //
335     //     m_biasedMarkCount = actualMarkCount + m_markCountBias.
336     //
337     // Marking an object will increment m_biasedMarkCount. Once 90 objects get marked, we will have
338     // m_biasedMarkCount = 0, which will trigger retirement. In other words, we want to set
339     // m_markCountBias like so:
340     //
341     //     m_markCountBias = -(minMarkedBlockUtilization * cellsPerBlock)
342     //
343     // All of this also means that you can detect if any objects are marked by doing:
344     //
345     //     m_biasedMarkCount != m_markCountBias
346     int16_t m_markCountBias;
347
348     HeapVersion m_markingVersion;
349     
350     Handle& m_handle;
351     VM* m_vm;
352 };
353
354 inline MarkedBlock::Handle& MarkedBlock::handle()
355 {
356     return m_handle;
357 }
358
359 inline MarkedBlock& MarkedBlock::Handle::block()
360 {
361     return *m_block;
362 }
363
364 inline size_t MarkedBlock::firstAtom()
365 {
366     return WTF::roundUpToMultipleOf<atomSize>(sizeof(MarkedBlock)) / atomSize;
367 }
368
369 inline MarkedBlock::Atom* MarkedBlock::atoms()
370 {
371     return reinterpret_cast<Atom*>(this);
372 }
373
374 inline bool MarkedBlock::isAtomAligned(const void* p)
375 {
376     return !(reinterpret_cast<Bits>(p) & atomAlignmentMask);
377 }
378
379 inline void* MarkedBlock::Handle::cellAlign(void* p)
380 {
381     Bits base = reinterpret_cast<Bits>(block().atoms() + firstAtom());
382     Bits bits = reinterpret_cast<Bits>(p);
383     bits -= base;
384     bits -= bits % cellSize();
385     bits += base;
386     return reinterpret_cast<void*>(bits);
387 }
388
389 inline MarkedBlock* MarkedBlock::blockFor(const void* p)
390 {
391     return reinterpret_cast<MarkedBlock*>(reinterpret_cast<Bits>(p) & blockMask);
392 }
393
394 inline MarkedAllocator* MarkedBlock::Handle::allocator() const
395 {
396     return m_allocator;
397 }
398
399 inline Subspace* MarkedBlock::Handle::subspace() const
400 {
401     return m_subspace;
402 }
403
404 inline Heap* MarkedBlock::Handle::heap() const
405 {
406     return m_weakSet.heap();
407 }
408
409 inline VM* MarkedBlock::Handle::vm() const
410 {
411     return m_weakSet.vm();
412 }
413
414 inline VM* MarkedBlock::vm() const
415 {
416     return m_vm;
417 }
418
419 inline WeakSet& MarkedBlock::Handle::weakSet()
420 {
421     return m_weakSet;
422 }
423
424 inline WeakSet& MarkedBlock::weakSet()
425 {
426     return m_handle.weakSet();
427 }
428
429 inline void MarkedBlock::Handle::shrink()
430 {
431     m_weakSet.shrink();
432 }
433
434 inline void MarkedBlock::Handle::visitWeakSet(SlotVisitor& visitor)
435 {
436     return m_weakSet.visit(visitor);
437 }
438
439 inline void MarkedBlock::Handle::reapWeakSet()
440 {
441     m_weakSet.reap();
442 }
443
444 inline size_t MarkedBlock::Handle::cellSize()
445 {
446     return m_atomsPerCell * atomSize;
447 }
448
449 inline size_t MarkedBlock::cellSize()
450 {
451     return m_handle.cellSize();
452 }
453
454 inline const AllocatorAttributes& MarkedBlock::Handle::attributes() const
455 {
456     return m_attributes;
457 }
458
459 inline const AllocatorAttributes& MarkedBlock::attributes() const
460 {
461     return m_handle.attributes();
462 }
463
464 inline bool MarkedBlock::Handle::needsDestruction() const
465 {
466     return m_attributes.destruction == NeedsDestruction;
467 }
468
469 inline DestructionMode MarkedBlock::Handle::destruction() const
470 {
471     return m_attributes.destruction;
472 }
473
474 inline HeapCell::Kind MarkedBlock::Handle::cellKind() const
475 {
476     return m_attributes.cellKind;
477 }
478
479 inline size_t MarkedBlock::Handle::markCount()
480 {
481     return m_block->markCount();
482 }
483
484 inline size_t MarkedBlock::Handle::size()
485 {
486     return markCount() * cellSize();
487 }
488
489 inline size_t MarkedBlock::atomNumber(const void* p)
490 {
491     return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
492 }
493
494 inline bool MarkedBlock::areMarksStale(HeapVersion markingVersion)
495 {
496     return markingVersion != m_markingVersion;
497 }
498
499 ALWAYS_INLINE DependencyWith<bool> MarkedBlock::areMarksStaleWithDependency(HeapVersion markingVersion)
500 {
501     HeapVersion version = m_markingVersion;
502     return dependencyWith(dependency(version), version != markingVersion);
503 }
504
505 inline Dependency MarkedBlock::aboutToMark(HeapVersion markingVersion)
506 {
507     auto result = areMarksStaleWithDependency(markingVersion);
508     if (UNLIKELY(result.value))
509         aboutToMarkSlow(markingVersion);
510     return result.dependency;
511 }
512
513 inline void MarkedBlock::Handle::assertMarksNotStale()
514 {
515     block().assertMarksNotStale();
516 }
517
518 inline bool MarkedBlock::isMarkedRaw(const void* p)
519 {
520     return m_marks.get(atomNumber(p));
521 }
522
523 inline bool MarkedBlock::isMarked(HeapVersion markingVersion, const void* p)
524 {
525     return areMarksStale(markingVersion) ? false : isMarkedRaw(p);
526 }
527
528 inline bool MarkedBlock::isMarkedConcurrently(HeapVersion markingVersion, const void* p)
529 {
530     auto result = areMarksStaleWithDependency(markingVersion);
531     if (result.value)
532         return false;
533     return m_marks.get(atomNumber(p), result.dependency);
534 }
535
536 inline bool MarkedBlock::isMarked(const void* p, Dependency dependency)
537 {
538     assertMarksNotStale();
539     return m_marks.get(atomNumber(p), dependency);
540 }
541
542 inline bool MarkedBlock::testAndSetMarked(const void* p, Dependency dependency)
543 {
544     assertMarksNotStale();
545     return m_marks.concurrentTestAndSet(atomNumber(p), dependency);
546 }
547
548 inline bool MarkedBlock::Handle::isNewlyAllocated(const void* p)
549 {
550     return m_newlyAllocated.get(m_block->atomNumber(p));
551 }
552
553 inline void MarkedBlock::Handle::setNewlyAllocated(const void* p)
554 {
555     m_newlyAllocated.set(m_block->atomNumber(p));
556 }
557
558 inline void MarkedBlock::Handle::clearNewlyAllocated(const void* p)
559 {
560     m_newlyAllocated.clear(m_block->atomNumber(p));
561 }
562
563 inline bool MarkedBlock::isAtom(const void* p)
564 {
565     ASSERT(MarkedBlock::isAtomAligned(p));
566     size_t atomNumber = this->atomNumber(p);
567     size_t firstAtom = MarkedBlock::firstAtom();
568     if (atomNumber < firstAtom) // Filters pointers into MarkedBlock metadata.
569         return false;
570     if ((atomNumber - firstAtom) % m_handle.m_atomsPerCell) // Filters pointers into cell middles.
571         return false;
572     if (atomNumber >= m_handle.m_endAtom) // Filters pointers into invalid cells out of the range.
573         return false;
574     return true;
575 }
576
577 template <typename Functor>
578 inline IterationStatus MarkedBlock::Handle::forEachCell(const Functor& functor)
579 {
580     HeapCell::Kind kind = m_attributes.cellKind;
581     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
582         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&m_block->atoms()[i]);
583         if (functor(cell, kind) == IterationStatus::Done)
584             return IterationStatus::Done;
585     }
586     return IterationStatus::Continue;
587 }
588
589 inline bool MarkedBlock::hasAnyMarked() const
590 {
591     return m_biasedMarkCount != m_markCountBias;
592 }
593
594 inline void MarkedBlock::noteMarked()
595 {
596     // This is racy by design. We don't want to pay the price of an atomic increment!
597     int16_t biasedMarkCount = m_biasedMarkCount;
598     ++biasedMarkCount;
599     m_biasedMarkCount = biasedMarkCount;
600     if (UNLIKELY(!biasedMarkCount))
601         noteMarkedSlow();
602 }
603
604 } // namespace JSC
605
606 namespace WTF {
607
608 struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
609     static unsigned hash(JSC::MarkedBlock* const& key)
610     {
611         // Aligned VM regions tend to be monotonically increasing integers,
612         // which is a great hash function, but we have to remove the low bits,
613         // since they're always zero, which is a terrible hash function!
614         return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
615     }
616 };
617
618 template<> struct DefaultHash<JSC::MarkedBlock*> {
619     typedef MarkedBlockHash Hash;
620 };
621
622 void printInternal(PrintStream& out, JSC::MarkedBlock::Handle::SweepMode);
623
624 } // namespace WTF