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