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