Speed up Heap::isMarkedConcurrently
[WebKit-https.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-2009, 2011, 2016 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 #ifndef MarkedBlock_h
23 #define MarkedBlock_h
24
25 #include "AllocatorAttributes.h"
26 #include "DestructionMode.h"
27 #include "FreeList.h"
28 #include "HeapCell.h"
29 #include "HeapOperation.h"
30 #include "IterationStatus.h"
31 #include "WeakSet.h"
32 #include <wtf/Bitmap.h>
33 #include <wtf/DataLog.h>
34 #include <wtf/DoublyLinkedList.h>
35 #include <wtf/HashFunctions.h>
36 #include <wtf/StdLibExtras.h>
37
38 namespace JSC {
39     
40 class Heap;
41 class JSCell;
42 class MarkedAllocator;
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         Heap* heap() const;
113         VM* vm() const;
114         WeakSet& weakSet();
115             
116         // Sweeping ensures that destructors get called and removes the block from the unswept
117         // set. Sweeping to free list also removes the block from the empty set, if it was in that
118         // set. Sweeping with SweepOnly may add this block to the empty set, if the block is found
119         // to be empty.
120         //
121         // Note that you need to make sure that the empty bit reflects reality. If it's not set
122         // and the block is freshly created, then we'll make the mistake of running destructors in
123         // the block. If it's not set and the block has nothing marked, then we'll make the
124         // mistake of making a pop freelist rather than a bump freelist.
125         enum SweepMode { SweepOnly, SweepToFreeList };
126         FreeList sweep(SweepMode = SweepOnly);
127         
128         void unsweepWithNoNewlyAllocated();
129         
130         void zap(const FreeList&);
131         
132         void shrink();
133             
134         unsigned visitWeakSet(HeapRootVisitor&);
135         void reapWeakSet();
136             
137         // While allocating from a free list, MarkedBlock temporarily has bogus
138         // cell liveness data. To restore accurate cell liveness data, call one
139         // of these functions:
140         void didConsumeFreeList(); // Call this once you've allocated all the items in the free list.
141         void stopAllocating(const FreeList&);
142         FreeList resumeAllocating(); // Call this if you canonicalized a block for some non-collection related purpose.
143             
144         // Returns true if the "newly allocated" bitmap was non-null 
145         // and was successfully cleared and false otherwise.
146         bool clearNewlyAllocated();
147             
148         size_t cellSize();
149         const AllocatorAttributes& attributes() const;
150         DestructionMode destruction() const;
151         bool needsDestruction() const;
152         HeapCell::Kind cellKind() const;
153             
154         size_t markCount();
155         size_t size();
156             
157         inline bool isLive(HeapVersion markingVersion, const HeapCell*);
158         inline bool isLiveCell(HeapVersion markingVersion, const void*);
159
160         bool isLive(const HeapCell*);
161         bool isLiveCell(const void*);
162
163         bool isMarkedOrNewlyAllocated(const HeapCell*);
164         bool isMarkedOrNewlyAllocated(HeapVersion markingVersion, const HeapCell*);
165             
166         bool isNewlyAllocated(const void*);
167         void setNewlyAllocated(const void*);
168         void clearNewlyAllocated(const void*);
169         
170         bool hasAnyNewlyAllocated() const { return !!m_newlyAllocated; }
171             
172         template <typename Functor> IterationStatus forEachCell(const Functor&);
173         template <typename Functor> inline IterationStatus forEachLiveCell(const Functor&);
174         template <typename Functor> inline IterationStatus forEachDeadCell(const Functor&);
175             
176         bool areMarksStale();
177         
178         void assertMarksNotStale();
179             
180         bool isFreeListed() const { return m_isFreeListed; }
181         
182         size_t index() const { return m_index; }
183         
184         void removeFromAllocator();
185         
186         void didAddToAllocator(MarkedAllocator*, size_t index);
187         void didRemoveFromAllocator();
188         
189     private:
190         Handle(Heap&, void*);
191             
192         template<DestructionMode>
193         FreeList sweepHelperSelectScribbleMode(SweepMode = SweepOnly);
194             
195         enum ScribbleMode { DontScribble, Scribble };
196             
197         template<DestructionMode, ScribbleMode>
198         FreeList sweepHelperSelectEmptyMode(SweepMode = SweepOnly);
199             
200         enum EmptyMode { IsEmpty, NotEmpty };
201         
202         template<EmptyMode, DestructionMode, ScribbleMode>
203         FreeList sweepHelperSelectHasNewlyAllocated(SweepMode = SweepOnly);
204         
205         enum NewlyAllocatedMode { HasNewlyAllocated, DoesNotHaveNewlyAllocated };
206         
207         template<EmptyMode, DestructionMode, ScribbleMode, NewlyAllocatedMode>
208         FreeList sweepHelperSelectSweepMode(SweepMode = SweepOnly);
209         
210         template<EmptyMode, SweepMode, DestructionMode, ScribbleMode, NewlyAllocatedMode>
211         FreeList sweepHelperSelectMarksMode();
212         
213         enum MarksMode { MarksStale, MarksNotStale };
214         
215         template<EmptyMode, SweepMode, DestructionMode, ScribbleMode, NewlyAllocatedMode, MarksMode>
216         FreeList specializedSweep();
217             
218         template<typename Func>
219         void forEachFreeCell(const FreeList&, const Func&);
220         
221         void setIsFreeListed();
222         
223         MarkedBlock::Handle* m_prev;
224         MarkedBlock::Handle* m_next;
225             
226         size_t m_atomsPerCell { std::numeric_limits<size_t>::max() };
227         size_t m_endAtom { std::numeric_limits<size_t>::max() }; // This is a fuzzy end. Always test for < m_endAtom.
228             
229         std::unique_ptr<WTF::Bitmap<atomsPerBlock>> m_newlyAllocated;
230             
231         AllocatorAttributes m_attributes;
232         bool m_isFreeListed { false };
233             
234         MarkedAllocator* m_allocator { nullptr };
235         size_t m_index { std::numeric_limits<size_t>::max() };
236         WeakSet m_weakSet;
237             
238         MarkedBlock* m_block { nullptr };
239     };
240         
241     static MarkedBlock::Handle* tryCreate(Heap&);
242         
243     Handle& handle();
244         
245     VM* vm() const;
246
247     static bool isAtomAligned(const void*);
248     static MarkedBlock* blockFor(const void*);
249     static size_t firstAtom();
250     size_t atomNumber(const void*);
251         
252     size_t markCount();
253
254     bool isMarked(const void*);
255     bool isMarked(HeapVersion markingVersion, const void*);
256     bool isMarkedConcurrently(HeapVersion markingVersion, const void*);
257     bool testAndSetMarked(const void*);
258         
259     bool isMarkedOrNewlyAllocated(const HeapCell*);
260     bool isMarkedOrNewlyAllocated(HeapVersion markingVersion, const HeapCell*);
261     
262     bool isAtom(const void*);
263     void clearMarked(const void*);
264     
265     size_t cellSize();
266     const AllocatorAttributes& attributes() const;
267     
268     bool hasAnyMarked() const;
269     void noteMarked();
270         
271     WeakSet& weakSet();
272
273     bool areMarksStale();
274     bool areMarksStale(HeapVersion markingVersion);
275     struct MarksWithDependency {
276         bool areStale;
277         ConsumeDependency dependency;
278     };
279     MarksWithDependency areMarksStaleWithDependency(HeapVersion markingVersion);
280     
281     void aboutToMark(HeapVersion markingVersion);
282         
283     void assertMarksNotStale();
284         
285     bool needsDestruction() const { return m_needsDestruction; }
286     
287     inline void resetMarkingVersion();
288     
289 private:
290     static const size_t atomAlignmentMask = atomSize - 1;
291
292     typedef char Atom[atomSize];
293
294     MarkedBlock(VM&, Handle&);
295     Atom* atoms();
296         
297     void aboutToMarkSlow(HeapVersion markingVersion);
298     void clearMarks();
299     void clearMarks(HeapVersion markingVersion);
300     void clearHasAnyMarked();
301     
302     void noteMarkedSlow();
303         
304     WTF::Bitmap<atomsPerBlock, WTF::BitmapAtomic, uint8_t> m_marks;
305
306     bool m_needsDestruction;
307     Lock m_lock;
308     
309     // The actual mark count can be computed by doing: m_biasedMarkCount - m_markCountBias. Note
310     // that this count is racy. It will accurately detect whether or not exactly zero things were
311     // marked, but if N things got marked, then this may report anything in the range [1, N] (or
312     // before unbiased, it would be [1 + m_markCountBias, N + m_markCountBias].)
313     int16_t m_biasedMarkCount;
314     
315     // We bias the mark count so that if m_biasedMarkCount >= 0 then the block should be retired.
316     // We go to all this trouble to make marking a bit faster: this way, marking knows when to
317     // retire a block using a js/jns on m_biasedMarkCount.
318     //
319     // For example, if a block has room for 100 objects and retirement happens whenever 90% are
320     // live, then m_markCountBias will be -90. This way, when marking begins, this will cause us to
321     // set m_biasedMarkCount to -90 as well, since:
322     //
323     //     m_biasedMarkCount = actualMarkCount + m_markCountBias.
324     //
325     // Marking an object will increment m_biasedMarkCount. Once 90 objects get marked, we will have
326     // m_biasedMarkCount = 0, which will trigger retirement. In other words, we want to set
327     // m_markCountBias like so:
328     //
329     //     m_markCountBias = -(minMarkedBlockUtilization * cellsPerBlock)
330     //
331     // All of this also means that you can detect if any objects are marked by doing:
332     //
333     //     m_biasedMarkCount != m_markCountBias
334     int16_t m_markCountBias;
335
336     HeapVersion m_markingVersion;
337     
338     Handle& m_handle;
339     VM* m_vm;
340 };
341
342 inline MarkedBlock::Handle& MarkedBlock::handle()
343 {
344     return m_handle;
345 }
346
347 inline MarkedBlock& MarkedBlock::Handle::block()
348 {
349     return *m_block;
350 }
351
352 inline size_t MarkedBlock::firstAtom()
353 {
354     return WTF::roundUpToMultipleOf<atomSize>(sizeof(MarkedBlock)) / atomSize;
355 }
356
357 inline MarkedBlock::Atom* MarkedBlock::atoms()
358 {
359     return reinterpret_cast<Atom*>(this);
360 }
361
362 inline bool MarkedBlock::isAtomAligned(const void* p)
363 {
364     return !(reinterpret_cast<Bits>(p) & atomAlignmentMask);
365 }
366
367 inline void* MarkedBlock::Handle::cellAlign(void* p)
368 {
369     Bits base = reinterpret_cast<Bits>(block().atoms() + firstAtom());
370     Bits bits = reinterpret_cast<Bits>(p);
371     bits -= base;
372     bits -= bits % cellSize();
373     bits += base;
374     return reinterpret_cast<void*>(bits);
375 }
376
377 inline MarkedBlock* MarkedBlock::blockFor(const void* p)
378 {
379     return reinterpret_cast<MarkedBlock*>(reinterpret_cast<Bits>(p) & blockMask);
380 }
381
382 inline MarkedAllocator* MarkedBlock::Handle::allocator() const
383 {
384     return m_allocator;
385 }
386
387 inline Heap* MarkedBlock::Handle::heap() const
388 {
389     return m_weakSet.heap();
390 }
391
392 inline VM* MarkedBlock::Handle::vm() const
393 {
394     return m_weakSet.vm();
395 }
396
397 inline VM* MarkedBlock::vm() const
398 {
399     return m_vm;
400 }
401
402 inline WeakSet& MarkedBlock::Handle::weakSet()
403 {
404     return m_weakSet;
405 }
406
407 inline WeakSet& MarkedBlock::weakSet()
408 {
409     return m_handle.weakSet();
410 }
411
412 inline void MarkedBlock::Handle::shrink()
413 {
414     m_weakSet.shrink();
415 }
416
417 inline unsigned MarkedBlock::Handle::visitWeakSet(HeapRootVisitor& heapRootVisitor)
418 {
419     return m_weakSet.visit(heapRootVisitor);
420 }
421
422 inline void MarkedBlock::Handle::reapWeakSet()
423 {
424     m_weakSet.reap();
425 }
426
427 inline size_t MarkedBlock::Handle::cellSize()
428 {
429     return m_atomsPerCell * atomSize;
430 }
431
432 inline size_t MarkedBlock::cellSize()
433 {
434     return m_handle.cellSize();
435 }
436
437 inline const AllocatorAttributes& MarkedBlock::Handle::attributes() const
438 {
439     return m_attributes;
440 }
441
442 inline const AllocatorAttributes& MarkedBlock::attributes() const
443 {
444     return m_handle.attributes();
445 }
446
447 inline bool MarkedBlock::Handle::needsDestruction() const
448 {
449     return m_attributes.destruction == NeedsDestruction;
450 }
451
452 inline DestructionMode MarkedBlock::Handle::destruction() const
453 {
454     return m_attributes.destruction;
455 }
456
457 inline HeapCell::Kind MarkedBlock::Handle::cellKind() const
458 {
459     return m_attributes.cellKind;
460 }
461
462 inline size_t MarkedBlock::Handle::markCount()
463 {
464     return m_block->markCount();
465 }
466
467 inline size_t MarkedBlock::Handle::size()
468 {
469     return markCount() * cellSize();
470 }
471
472 inline size_t MarkedBlock::atomNumber(const void* p)
473 {
474     return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
475 }
476
477 inline bool MarkedBlock::areMarksStale(HeapVersion markingVersion)
478 {
479     return markingVersion != m_markingVersion;
480 }
481
482 ALWAYS_INLINE MarkedBlock::MarksWithDependency MarkedBlock::areMarksStaleWithDependency(HeapVersion markingVersion)
483 {
484     auto consumed = consumeLoad(&m_markingVersion);
485     MarksWithDependency ret;
486     ret.areStale = consumed.value != markingVersion;
487     ret.dependency = consumed.dependency;
488     return ret;
489 }
490
491 inline void MarkedBlock::aboutToMark(HeapVersion markingVersion)
492 {
493     if (UNLIKELY(areMarksStale(markingVersion)))
494         aboutToMarkSlow(markingVersion);
495     WTF::loadLoadFence();
496 }
497
498 #if ASSERT_DISABLED
499 inline void MarkedBlock::assertMarksNotStale()
500 {
501 }
502 #endif // ASSERT_DISABLED
503
504 inline void MarkedBlock::Handle::assertMarksNotStale()
505 {
506     block().assertMarksNotStale();
507 }
508
509 inline bool MarkedBlock::isMarked(HeapVersion markingVersion, const void* p)
510 {
511     return areMarksStale(markingVersion) ? false : m_marks.get(atomNumber(p));
512 }
513
514 inline bool MarkedBlock::isMarkedConcurrently(HeapVersion markingVersion, const void* p)
515 {
516     auto marksWithDependency = areMarksStaleWithDependency(markingVersion);
517     if (marksWithDependency.areStale)
518         return false;
519     return m_marks.get(atomNumber(p) + marksWithDependency.dependency);
520 }
521
522 inline bool MarkedBlock::testAndSetMarked(const void* p)
523 {
524     assertMarksNotStale();
525     return m_marks.concurrentTestAndSet(atomNumber(p));
526 }
527
528 inline bool MarkedBlock::Handle::isNewlyAllocated(const void* p)
529 {
530     return m_newlyAllocated->get(m_block->atomNumber(p));
531 }
532
533 inline void MarkedBlock::Handle::setNewlyAllocated(const void* p)
534 {
535     m_newlyAllocated->set(m_block->atomNumber(p));
536 }
537
538 inline void MarkedBlock::Handle::clearNewlyAllocated(const void* p)
539 {
540     m_newlyAllocated->clear(m_block->atomNumber(p));
541 }
542
543 inline bool MarkedBlock::Handle::clearNewlyAllocated()
544 {
545     if (m_newlyAllocated) {
546         m_newlyAllocated = nullptr;
547         return true;
548     }
549     return false;
550 }
551
552 inline bool MarkedBlock::Handle::isMarkedOrNewlyAllocated(HeapVersion markingVersion, const HeapCell* cell)
553 {
554     return m_block->isMarked(markingVersion, cell) || (m_newlyAllocated && isNewlyAllocated(cell));
555 }
556
557 inline bool MarkedBlock::isMarkedOrNewlyAllocated(HeapVersion markingVersion, const HeapCell* cell)
558 {
559     return isMarked(markingVersion, cell) || (m_handle.m_newlyAllocated && m_handle.isNewlyAllocated(cell));
560 }
561
562 inline bool MarkedBlock::isAtom(const void* p)
563 {
564     ASSERT(MarkedBlock::isAtomAligned(p));
565     size_t atomNumber = this->atomNumber(p);
566     size_t firstAtom = MarkedBlock::firstAtom();
567     if (atomNumber < firstAtom) // Filters pointers into MarkedBlock metadata.
568         return false;
569     if ((atomNumber - firstAtom) % m_handle.m_atomsPerCell) // Filters pointers into cell middles.
570         return false;
571     if (atomNumber >= m_handle.m_endAtom) // Filters pointers into invalid cells out of the range.
572         return false;
573     return true;
574 }
575
576 template <typename Functor>
577 inline IterationStatus MarkedBlock::Handle::forEachCell(const Functor& functor)
578 {
579     HeapCell::Kind kind = m_attributes.cellKind;
580     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
581         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&m_block->atoms()[i]);
582         if (functor(cell, kind) == IterationStatus::Done)
583             return IterationStatus::Done;
584     }
585     return IterationStatus::Continue;
586 }
587
588 inline bool MarkedBlock::hasAnyMarked() const
589 {
590     return m_biasedMarkCount != m_markCountBias;
591 }
592
593 inline void MarkedBlock::noteMarked()
594 {
595     // This is racy by design. We don't want to pay the price of an atomic increment!
596     int16_t biasedMarkCount = m_biasedMarkCount;
597     ++biasedMarkCount;
598     m_biasedMarkCount = biasedMarkCount;
599     if (UNLIKELY(!biasedMarkCount))
600         noteMarkedSlow();
601 }
602
603 } // namespace JSC
604
605 namespace WTF {
606
607 struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
608     static unsigned hash(JSC::MarkedBlock* const& key)
609     {
610         // Aligned VM regions tend to be monotonically increasing integers,
611         // which is a great hash function, but we have to remove the low bits,
612         // since they're always zero, which is a terrible hash function!
613         return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
614     }
615 };
616
617 template<> struct DefaultHash<JSC::MarkedBlock*> {
618     typedef MarkedBlockHash Hash;
619 };
620
621 void printInternal(PrintStream& out, JSC::MarkedBlock::Handle::SweepMode);
622
623 } // namespace WTF
624
625 #endif // MarkedBlock_h