b38c7e75682f54817091a03fdafc12026ffa5b8e
[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 // Set to log state transitions of blocks.
48 #define HEAP_LOG_BLOCK_STATE_TRANSITIONS 0
49
50 #if HEAP_LOG_BLOCK_STATE_TRANSITIONS
51 #define HEAP_LOG_BLOCK_STATE_TRANSITION(handle) do {            \
52         dataLogF(                                               \
53             "%s:%d %s: block %s = %p, %d\n",                    \
54             __FILE__, __LINE__, __FUNCTION__,                   \
55             #handle, &(handle)->block(), (handle)->m_state);    \
56     } while (false)
57 #else
58 #define HEAP_LOG_BLOCK_STATE_TRANSITION(handle) ((void)0)
59 #endif
60
61 // A marked block is a page-aligned container for heap-allocated objects.
62 // Objects are allocated within cells of the marked block. For a given
63 // marked block, all cells have the same size. Objects smaller than the
64 // cell size may be allocated in the marked block, in which case the
65 // allocation suffers from internal fragmentation: wasted space whose
66 // size is equal to the difference between the cell size and the object
67 // size.
68
69 class MarkedBlock {
70     WTF_MAKE_NONCOPYABLE(MarkedBlock);
71     friend class LLIntOffsetsExtractor;
72     friend struct VerifyMarked;
73
74 public:
75     class Handle;
76 private:
77     friend class Handle;
78 public:
79     enum BlockState : uint8_t { New, FreeListed, Allocated, Marked };
80         
81     static const size_t atomSize = 16; // bytes
82     static const size_t blockSize = 16 * KB;
83     static const size_t blockMask = ~(blockSize - 1); // blockSize must be a power of two.
84
85     static const size_t atomsPerBlock = blockSize / atomSize;
86
87     static_assert(!(MarkedBlock::atomSize & (MarkedBlock::atomSize - 1)), "MarkedBlock::atomSize must be a power of two.");
88     static_assert(!(MarkedBlock::blockSize & (MarkedBlock::blockSize - 1)), "MarkedBlock::blockSize must be a power of two.");
89
90     struct VoidFunctor {
91         typedef void ReturnType;
92         void returnValue() { }
93     };
94
95     class CountFunctor {
96     public:
97         typedef size_t ReturnType;
98
99         CountFunctor() : m_count(0) { }
100         void count(size_t count) const { m_count += count; }
101         ReturnType returnValue() const { return m_count; }
102
103     private:
104         // FIXME: This is mutable because we're using a functor rather than C++ lambdas.
105         // https://bugs.webkit.org/show_bug.cgi?id=159644
106         mutable ReturnType m_count;
107     };
108         
109     class Handle : public BasicRawSentinelNode<Handle> {
110         WTF_MAKE_NONCOPYABLE(Handle);
111         WTF_MAKE_FAST_ALLOCATED;
112         friend class DoublyLinkedListNode<Handle>;
113         friend class LLIntOffsetsExtractor;
114         friend class MarkedBlock;
115         friend struct VerifyMarked;
116     public:
117             
118         ~Handle();
119             
120         MarkedBlock& block();
121             
122         void* cellAlign(void*);
123             
124         bool isEmpty();
125
126         void lastChanceToFinalize();
127
128         MarkedAllocator* allocator() const;
129         Heap* heap() const;
130         VM* vm() const;
131         WeakSet& weakSet();
132             
133         enum SweepMode { SweepOnly, SweepToFreeList };
134         FreeList sweep(SweepMode = SweepOnly);
135         
136         void unsweepWithNoNewlyAllocated();
137         
138         void zap(const FreeList&);
139         
140         void shrink();
141             
142         unsigned visitWeakSet(HeapRootVisitor&);
143         void reapWeakSet();
144             
145         // While allocating from a free list, MarkedBlock temporarily has bogus
146         // cell liveness data. To restore accurate cell liveness data, call one
147         // of these functions:
148         void didConsumeFreeList(); // Call this once you've allocated all the items in the free list.
149         void stopAllocating(const FreeList&);
150         FreeList resumeAllocating(); // Call this if you canonicalized a block for some non-collection related purpose.
151             
152         // Returns true if the "newly allocated" bitmap was non-null 
153         // and was successfully cleared and false otherwise.
154         bool clearNewlyAllocated();
155             
156         void flipForEdenCollection();
157             
158         size_t cellSize();
159         const AllocatorAttributes& attributes() const;
160         DestructionMode destruction() const;
161         bool needsDestruction() const;
162         HeapCell::Kind cellKind() const;
163             
164         size_t markCount();
165         size_t size();
166             
167         bool isLive(const HeapCell*);
168         bool isLiveCell(const void*);
169         bool isMarkedOrNewlyAllocated(const HeapCell*);
170             
171         bool isNewlyAllocated(const void*);
172         void setNewlyAllocated(const void*);
173         void clearNewlyAllocated(const void*);
174         
175         bool hasAnyNewlyAllocated() const { return !!m_newlyAllocated; }
176             
177         bool isAllocated() const;
178         bool isMarked() const;
179         bool isFreeListed() const;
180         bool needsSweeping() const;
181         void willRemoveBlock();
182
183         template <typename Functor> IterationStatus forEachCell(const Functor&);
184         template <typename Functor> IterationStatus forEachLiveCell(const Functor&);
185         template <typename Functor> IterationStatus forEachDeadCell(const Functor&);
186             
187         bool needsFlip();
188             
189         void flipIfNecessaryConcurrently(HeapVersion);
190         void flipIfNecessary(HeapVersion);
191         void flipIfNecessary();
192             
193         void assertFlipped();
194             
195         bool isOnBlocksToSweep() const { return m_isOnBlocksToSweep; }
196         void setIsOnBlocksToSweep(bool value) { m_isOnBlocksToSweep = value; }
197         
198         BlockState state() const { return m_state; }
199             
200     private:
201         Handle(Heap&, MarkedAllocator*, size_t cellSize, const AllocatorAttributes&, void*);
202             
203         template<DestructionMode>
204         FreeList sweepHelperSelectScribbleMode(SweepMode = SweepOnly);
205             
206         enum ScribbleMode { DontScribble, Scribble };
207             
208         template<DestructionMode, ScribbleMode>
209         FreeList sweepHelperSelectStateAndSweepMode(SweepMode = SweepOnly);
210             
211         enum NewlyAllocatedMode { HasNewlyAllocated, DoesNotHaveNewlyAllocated };
212             
213         template<BlockState, SweepMode, DestructionMode, ScribbleMode, NewlyAllocatedMode>
214         FreeList specializedSweep();
215             
216         template<typename Func>
217         void forEachFreeCell(const FreeList&, const Func&);
218             
219         MarkedBlock::Handle* m_prev;
220         MarkedBlock::Handle* m_next;
221             
222         size_t m_atomsPerCell;
223         size_t m_endAtom; // This is a fuzzy end. Always test for < m_endAtom.
224             
225         std::unique_ptr<WTF::Bitmap<atomsPerBlock>> m_newlyAllocated;
226             
227         AllocatorAttributes m_attributes;
228         BlockState m_state;
229         bool m_isOnBlocksToSweep { false };
230             
231         MarkedAllocator* m_allocator;
232         WeakSet m_weakSet;
233             
234         MarkedBlock* m_block;
235     };
236         
237     static MarkedBlock::Handle* tryCreate(Heap&, MarkedAllocator*, size_t cellSize, const AllocatorAttributes&);
238         
239     Handle& handle();
240         
241     VM* vm() const;
242
243     static bool isAtomAligned(const void*);
244     static MarkedBlock* blockFor(const void*);
245     static size_t firstAtom();
246     size_t atomNumber(const void*);
247         
248     size_t markCount();
249
250     bool isMarked(const void*);
251     bool testAndSetMarked(const void*);
252         
253     bool isMarkedOrNewlyAllocated(const HeapCell*);
254
255     bool isAtom(const void*);
256     void setMarked(const void*);
257     void clearMarked(const void*);
258         
259     size_t cellSize();
260     const AllocatorAttributes& attributes() const;
261
262     bool hasAnyMarked() const;
263     void noteMarked();
264         
265     WeakSet& weakSet();
266
267     bool needsFlip();
268         
269     void flipIfNecessaryConcurrently(HeapVersion);
270     void flipIfNecessary(HeapVersion);
271     void flipIfNecessary();
272         
273     void assertFlipped();
274         
275     bool needsDestruction() const { return m_needsDestruction; }
276         
277 private:
278     static const size_t atomAlignmentMask = atomSize - 1;
279
280     typedef char Atom[atomSize];
281
282     MarkedBlock(VM&, Handle&);
283     Atom* atoms();
284         
285     void flipIfNecessaryConcurrentlySlow();
286     void flipIfNecessarySlow();
287     void clearMarks();
288     void clearHasAnyMarked();
289     
290     void noteMarkedSlow();
291         
292     WTF::Bitmap<atomsPerBlock, WTF::BitmapAtomic, uint8_t> m_marks;
293
294     bool m_needsDestruction;
295     Lock m_lock;
296     
297     // The actual mark count can be computed by doing: m_biasedMarkCount - m_markCountBias. Note
298     // that this count is racy. It will accurately detect whether or not exactly zero things were
299     // marked, but if N things got marked, then this may report anything in the range [1, N] (or
300     // before unbiased, it would be [1 + m_markCountBias, N + m_markCountBias].)
301     int16_t m_biasedMarkCount;
302     
303     // We bias the mark count so that if m_biasedMarkCount >= 0 then the block should be retired.
304     // We go to all this trouble to make marking a bit faster: this way, marking knows when to
305     // retire a block using a js/jns on m_biasedMarkCount.
306     //
307     // For example, if a block has room for 100 objects and retirement happens whenever 90% are
308     // live, then m_markCountBias will be -90. This way, when marking begins, this will cause us to
309     // set m_biasedMarkCount to -90 as well, since:
310     //
311     //     m_biasedMarkCount = actualMarkCount + m_markCountBias.
312     //
313     // Marking an object will increment m_biasedMarkCount. Once 90 objects get marked, we will have
314     // m_biasedMarkCount = 0, which will trigger retirement. In other words, we want to set
315     // m_markCountBias like so:
316     //
317     //     m_markCountBias = -(minMarkedBlockUtilization * cellsPerBlock)
318     //
319     // All of this also means that you can detect if any objects are marked by doing:
320     //
321     //     m_biasedMarkCount != m_markCountBias
322     int16_t m_markCountBias;
323
324     HeapVersion m_version;
325     
326     Handle& m_handle;
327     VM* m_vm;
328 };
329
330 inline MarkedBlock::Handle& MarkedBlock::handle()
331 {
332     return m_handle;
333 }
334
335 inline MarkedBlock& MarkedBlock::Handle::block()
336 {
337     return *m_block;
338 }
339
340 inline size_t MarkedBlock::firstAtom()
341 {
342     return WTF::roundUpToMultipleOf<atomSize>(sizeof(MarkedBlock)) / atomSize;
343 }
344
345 inline MarkedBlock::Atom* MarkedBlock::atoms()
346 {
347     return reinterpret_cast<Atom*>(this);
348 }
349
350 inline bool MarkedBlock::isAtomAligned(const void* p)
351 {
352     return !(reinterpret_cast<Bits>(p) & atomAlignmentMask);
353 }
354
355 inline void* MarkedBlock::Handle::cellAlign(void* p)
356 {
357     Bits base = reinterpret_cast<Bits>(block().atoms() + firstAtom());
358     Bits bits = reinterpret_cast<Bits>(p);
359     bits -= base;
360     bits -= bits % cellSize();
361     bits += base;
362     return reinterpret_cast<void*>(bits);
363 }
364
365 inline MarkedBlock* MarkedBlock::blockFor(const void* p)
366 {
367     return reinterpret_cast<MarkedBlock*>(reinterpret_cast<Bits>(p) & blockMask);
368 }
369
370 inline MarkedAllocator* MarkedBlock::Handle::allocator() const
371 {
372     return m_allocator;
373 }
374
375 inline Heap* MarkedBlock::Handle::heap() const
376 {
377     return m_weakSet.heap();
378 }
379
380 inline VM* MarkedBlock::Handle::vm() const
381 {
382     return m_weakSet.vm();
383 }
384
385 inline VM* MarkedBlock::vm() const
386 {
387     return m_vm;
388 }
389
390 inline WeakSet& MarkedBlock::Handle::weakSet()
391 {
392     return m_weakSet;
393 }
394
395 inline WeakSet& MarkedBlock::weakSet()
396 {
397     return m_handle.weakSet();
398 }
399
400 inline void MarkedBlock::Handle::shrink()
401 {
402     m_weakSet.shrink();
403 }
404
405 inline unsigned MarkedBlock::Handle::visitWeakSet(HeapRootVisitor& heapRootVisitor)
406 {
407     return m_weakSet.visit(heapRootVisitor);
408 }
409
410 inline void MarkedBlock::Handle::reapWeakSet()
411 {
412     m_weakSet.reap();
413 }
414
415 inline size_t MarkedBlock::Handle::cellSize()
416 {
417     return m_atomsPerCell * atomSize;
418 }
419
420 inline size_t MarkedBlock::cellSize()
421 {
422     return m_handle.cellSize();
423 }
424
425 inline const AllocatorAttributes& MarkedBlock::Handle::attributes() const
426 {
427     return m_attributes;
428 }
429
430 inline const AllocatorAttributes& MarkedBlock::attributes() const
431 {
432     return m_handle.attributes();
433 }
434
435 inline bool MarkedBlock::Handle::needsDestruction() const
436 {
437     return m_attributes.destruction == NeedsDestruction;
438 }
439
440 inline DestructionMode MarkedBlock::Handle::destruction() const
441 {
442     return m_attributes.destruction;
443 }
444
445 inline HeapCell::Kind MarkedBlock::Handle::cellKind() const
446 {
447     return m_attributes.cellKind;
448 }
449
450 inline size_t MarkedBlock::Handle::markCount()
451 {
452     return m_block->markCount();
453 }
454
455 inline size_t MarkedBlock::Handle::size()
456 {
457     return markCount() * cellSize();
458 }
459
460 inline size_t MarkedBlock::atomNumber(const void* p)
461 {
462     return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
463 }
464
465 inline void MarkedBlock::flipIfNecessary(HeapVersion heapVersion)
466 {
467     if (UNLIKELY(heapVersion != m_version))
468         flipIfNecessarySlow();
469 }
470
471 inline void MarkedBlock::flipIfNecessaryConcurrently(HeapVersion heapVersion)
472 {
473     if (UNLIKELY(heapVersion != m_version))
474         flipIfNecessaryConcurrentlySlow();
475     WTF::loadLoadFence();
476 }
477
478 inline void MarkedBlock::Handle::flipIfNecessary(HeapVersion heapVersion)
479 {
480     block().flipIfNecessary(heapVersion);
481 }
482
483 inline void MarkedBlock::Handle::flipIfNecessaryConcurrently(HeapVersion heapVersion)
484 {
485     block().flipIfNecessaryConcurrently(heapVersion);
486 }
487
488 inline void MarkedBlock::Handle::flipForEdenCollection()
489 {
490     assertFlipped();
491         
492     HEAP_LOG_BLOCK_STATE_TRANSITION(this);
493     
494     ASSERT(m_state != New && m_state != FreeListed);
495     
496     m_state = Marked;
497 }
498
499 #if ASSERT_DISABLED
500 inline void MarkedBlock::assertFlipped()
501 {
502 }
503 #endif // ASSERT_DISABLED
504
505 inline void MarkedBlock::Handle::assertFlipped()
506 {
507     block().assertFlipped();
508 }
509
510 inline bool MarkedBlock::isMarked(const void* p)
511 {
512     assertFlipped();
513     return m_marks.get(atomNumber(p));
514 }
515
516 inline bool MarkedBlock::testAndSetMarked(const void* p)
517 {
518     assertFlipped();
519     return m_marks.concurrentTestAndSet(atomNumber(p));
520 }
521
522 inline bool MarkedBlock::Handle::isNewlyAllocated(const void* p)
523 {
524     return m_newlyAllocated->get(m_block->atomNumber(p));
525 }
526
527 inline void MarkedBlock::Handle::setNewlyAllocated(const void* p)
528 {
529     m_newlyAllocated->set(m_block->atomNumber(p));
530 }
531
532 inline void MarkedBlock::Handle::clearNewlyAllocated(const void* p)
533 {
534     m_newlyAllocated->clear(m_block->atomNumber(p));
535 }
536
537 inline bool MarkedBlock::Handle::clearNewlyAllocated()
538 {
539     if (m_newlyAllocated) {
540         m_newlyAllocated = nullptr;
541         return true;
542     }
543     return false;
544 }
545
546 inline bool MarkedBlock::Handle::isMarkedOrNewlyAllocated(const HeapCell* cell)
547 {
548     ASSERT(m_state == Marked);
549     return m_block->isMarked(cell) || (m_newlyAllocated && isNewlyAllocated(cell));
550 }
551
552 inline bool MarkedBlock::isMarkedOrNewlyAllocated(const HeapCell* cell)
553 {
554     ASSERT(m_handle.m_state == Marked);
555     return isMarked(cell) || (m_handle.m_newlyAllocated && m_handle.isNewlyAllocated(cell));
556 }
557
558 inline bool MarkedBlock::Handle::isLive(const HeapCell* cell)
559 {
560     assertFlipped();
561     switch (m_state) {
562     case Allocated:
563         return true;
564
565     case Marked:
566         return isMarkedOrNewlyAllocated(cell);
567
568     case New:
569     case FreeListed:
570         RELEASE_ASSERT_NOT_REACHED();
571         return false;
572     }
573
574     RELEASE_ASSERT_NOT_REACHED();
575     return false;
576 }
577
578 inline bool MarkedBlock::isAtom(const void* p)
579 {
580     ASSERT(MarkedBlock::isAtomAligned(p));
581     size_t atomNumber = this->atomNumber(p);
582     size_t firstAtom = MarkedBlock::firstAtom();
583     if (atomNumber < firstAtom) // Filters pointers into MarkedBlock metadata.
584         return false;
585     if ((atomNumber - firstAtom) % m_handle.m_atomsPerCell) // Filters pointers into cell middles.
586         return false;
587     if (atomNumber >= m_handle.m_endAtom) // Filters pointers into invalid cells out of the range.
588         return false;
589     return true;
590 }
591
592 inline bool MarkedBlock::Handle::isLiveCell(const void* p)
593 {
594     if (!m_block->isAtom(p))
595         return false;
596     return isLive(static_cast<const HeapCell*>(p));
597 }
598
599 template <typename Functor>
600 inline IterationStatus MarkedBlock::Handle::forEachCell(const Functor& functor)
601 {
602     HeapCell::Kind kind = m_attributes.cellKind;
603     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
604         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&m_block->atoms()[i]);
605         if (functor(cell, kind) == IterationStatus::Done)
606             return IterationStatus::Done;
607     }
608     return IterationStatus::Continue;
609 }
610
611 template <typename Functor>
612 inline IterationStatus MarkedBlock::Handle::forEachLiveCell(const Functor& functor)
613 {
614     flipIfNecessary();
615     HeapCell::Kind kind = m_attributes.cellKind;
616     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
617         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&m_block->atoms()[i]);
618         if (!isLive(cell))
619             continue;
620
621         if (functor(cell, kind) == IterationStatus::Done)
622             return IterationStatus::Done;
623     }
624     return IterationStatus::Continue;
625 }
626
627 template <typename Functor>
628 inline IterationStatus MarkedBlock::Handle::forEachDeadCell(const Functor& functor)
629 {
630     flipIfNecessary();
631     HeapCell::Kind kind = m_attributes.cellKind;
632     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
633         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&m_block->atoms()[i]);
634         if (isLive(cell))
635             continue;
636
637         if (functor(cell, kind) == IterationStatus::Done)
638             return IterationStatus::Done;
639     }
640     return IterationStatus::Continue;
641 }
642
643 inline bool MarkedBlock::Handle::needsSweeping() const
644 {
645     const_cast<MarkedBlock::Handle*>(this)->flipIfNecessary();
646     return m_state == Marked;
647 }
648
649 inline bool MarkedBlock::Handle::isAllocated() const
650 {
651     const_cast<MarkedBlock::Handle*>(this)->flipIfNecessary();
652     return m_state == Allocated;
653 }
654
655 inline bool MarkedBlock::Handle::isMarked() const
656 {
657     const_cast<MarkedBlock::Handle*>(this)->flipIfNecessary();
658     return m_state == Marked;
659 }
660
661 inline bool MarkedBlock::Handle::isFreeListed() const
662 {
663     const_cast<MarkedBlock::Handle*>(this)->flipIfNecessary();
664     return m_state == FreeListed;
665 }
666
667 inline bool MarkedBlock::hasAnyMarked() const
668 {
669     return m_biasedMarkCount != m_markCountBias;
670 }
671
672 inline void MarkedBlock::noteMarked()
673 {
674     // This is racy by design. We don't want to pay the price of an atomic increment!
675     int16_t biasedMarkCount = m_biasedMarkCount;
676     ++biasedMarkCount;
677     m_biasedMarkCount = biasedMarkCount;
678     if (UNLIKELY(!biasedMarkCount))
679         noteMarkedSlow();
680 }
681
682 } // namespace JSC
683
684 namespace WTF {
685
686 struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
687     static unsigned hash(JSC::MarkedBlock* const& key)
688     {
689         // Aligned VM regions tend to be monotonically increasing integers,
690         // which is a great hash function, but we have to remove the low bits,
691         // since they're always zero, which is a terrible hash function!
692         return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
693     }
694 };
695
696 template<> struct DefaultHash<JSC::MarkedBlock*> {
697     typedef MarkedBlockHash Hash;
698 };
699
700 void printInternal(PrintStream& out, JSC::MarkedBlock::BlockState);
701
702 } // namespace WTF
703
704 #endif // MarkedBlock_h