78c91e2dab7b24001f3007a24a36c030c3ecb083
[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 #pragma once
23
24 #include "AllocatorAttributes.h"
25 #include "DestructionMode.h"
26 #include "FreeList.h"
27 #include "HeapCell.h"
28 #include "HeapOperation.h"
29 #include "IterationStatus.h"
30 #include "WeakSet.h"
31 #include <wtf/Atomics.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 isNewlyAllocated(const void*);
164         void setNewlyAllocated(const void*);
165         void clearNewlyAllocated(const void*);
166         
167         bool hasAnyNewlyAllocated() const { return !!m_newlyAllocated; }
168             
169         template <typename Functor> IterationStatus forEachCell(const Functor&);
170         template <typename Functor> inline IterationStatus forEachLiveCell(const Functor&);
171         template <typename Functor> inline IterationStatus forEachDeadCell(const Functor&);
172             
173         bool areMarksStale();
174         
175         void assertMarksNotStale();
176             
177         bool isFreeListed() const { return m_isFreeListed; }
178         
179         size_t index() const { return m_index; }
180         
181         void removeFromAllocator();
182         
183         void didAddToAllocator(MarkedAllocator*, size_t index);
184         void didRemoveFromAllocator();
185         
186     private:
187         Handle(Heap&, void*);
188             
189         template<DestructionMode>
190         FreeList sweepHelperSelectScribbleMode(SweepMode = SweepOnly);
191             
192         enum ScribbleMode { DontScribble, Scribble };
193             
194         template<DestructionMode, ScribbleMode>
195         FreeList sweepHelperSelectEmptyMode(SweepMode = SweepOnly);
196             
197         enum EmptyMode { IsEmpty, NotEmpty };
198         
199         template<EmptyMode, DestructionMode, ScribbleMode>
200         FreeList sweepHelperSelectHasNewlyAllocated(SweepMode = SweepOnly);
201         
202         enum NewlyAllocatedMode { HasNewlyAllocated, DoesNotHaveNewlyAllocated };
203         
204         template<EmptyMode, DestructionMode, ScribbleMode, NewlyAllocatedMode>
205         FreeList sweepHelperSelectSweepMode(SweepMode = SweepOnly);
206         
207         template<EmptyMode, SweepMode, DestructionMode, ScribbleMode, NewlyAllocatedMode>
208         FreeList sweepHelperSelectMarksMode();
209         
210         enum MarksMode { MarksStale, MarksNotStale };
211         
212         template<EmptyMode, SweepMode, DestructionMode, ScribbleMode, NewlyAllocatedMode, MarksMode>
213         FreeList specializedSweep();
214             
215         template<typename Func>
216         void forEachFreeCell(const FreeList&, const Func&);
217         
218         void setIsFreeListed();
219         
220         MarkedBlock::Handle* m_prev;
221         MarkedBlock::Handle* m_next;
222             
223         size_t m_atomsPerCell { std::numeric_limits<size_t>::max() };
224         size_t m_endAtom { std::numeric_limits<size_t>::max() }; // This is a fuzzy end. Always test for < m_endAtom.
225             
226         std::unique_ptr<WTF::Bitmap<atomsPerBlock>> m_newlyAllocated;
227             
228         AllocatorAttributes m_attributes;
229         bool m_isFreeListed { false };
230             
231         MarkedAllocator* m_allocator { nullptr };
232         size_t m_index { std::numeric_limits<size_t>::max() };
233         WeakSet m_weakSet;
234             
235         MarkedBlock* m_block { nullptr };
236     };
237         
238     static MarkedBlock::Handle* tryCreate(Heap&);
239         
240     Handle& handle();
241         
242     VM* vm() const;
243
244     static bool isAtomAligned(const void*);
245     static MarkedBlock* blockFor(const void*);
246     static size_t firstAtom();
247     size_t atomNumber(const void*);
248         
249     size_t markCount();
250
251     bool isMarked(const void*);
252     bool isMarked(HeapVersion markingVersion, const void*);
253     bool isMarkedConcurrently(HeapVersion markingVersion, const void*);
254     bool testAndSetMarked(const void*);
255         
256     bool isAtom(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 areMarksStale();
268     bool areMarksStale(HeapVersion markingVersion);
269     struct MarksWithDependency {
270         bool areStale;
271         ConsumeDependency dependency;
272     };
273     MarksWithDependency areMarksStaleWithDependency(HeapVersion markingVersion);
274     
275     void aboutToMark(HeapVersion markingVersion);
276         
277     void assertMarksNotStale();
278         
279     bool needsDestruction() const { return m_needsDestruction; }
280     
281     inline void resetMarkingVersion();
282     
283 private:
284     static const size_t atomAlignmentMask = atomSize - 1;
285
286     typedef char Atom[atomSize];
287
288     MarkedBlock(VM&, Handle&);
289     Atom* atoms();
290         
291     void aboutToMarkSlow(HeapVersion markingVersion);
292     void clearMarks();
293     void clearMarks(HeapVersion markingVersion);
294     void clearHasAnyMarked();
295     
296     void noteMarkedSlow();
297         
298     WTF::Bitmap<atomsPerBlock, WTF::BitmapAtomic, uint8_t> m_marks;
299
300     bool m_needsDestruction;
301     Lock m_lock;
302     
303     // The actual mark count can be computed by doing: m_biasedMarkCount - m_markCountBias. Note
304     // that this count is racy. It will accurately detect whether or not exactly zero things were
305     // marked, but if N things got marked, then this may report anything in the range [1, N] (or
306     // before unbiased, it would be [1 + m_markCountBias, N + m_markCountBias].)
307     int16_t m_biasedMarkCount;
308     
309     // We bias the mark count so that if m_biasedMarkCount >= 0 then the block should be retired.
310     // We go to all this trouble to make marking a bit faster: this way, marking knows when to
311     // retire a block using a js/jns on m_biasedMarkCount.
312     //
313     // For example, if a block has room for 100 objects and retirement happens whenever 90% are
314     // live, then m_markCountBias will be -90. This way, when marking begins, this will cause us to
315     // set m_biasedMarkCount to -90 as well, since:
316     //
317     //     m_biasedMarkCount = actualMarkCount + m_markCountBias.
318     //
319     // Marking an object will increment m_biasedMarkCount. Once 90 objects get marked, we will have
320     // m_biasedMarkCount = 0, which will trigger retirement. In other words, we want to set
321     // m_markCountBias like so:
322     //
323     //     m_markCountBias = -(minMarkedBlockUtilization * cellsPerBlock)
324     //
325     // All of this also means that you can detect if any objects are marked by doing:
326     //
327     //     m_biasedMarkCount != m_markCountBias
328     int16_t m_markCountBias;
329
330     HeapVersion m_markingVersion;
331     
332     Handle& m_handle;
333     VM* m_vm;
334 };
335
336 inline MarkedBlock::Handle& MarkedBlock::handle()
337 {
338     return m_handle;
339 }
340
341 inline MarkedBlock& MarkedBlock::Handle::block()
342 {
343     return *m_block;
344 }
345
346 inline size_t MarkedBlock::firstAtom()
347 {
348     return WTF::roundUpToMultipleOf<atomSize>(sizeof(MarkedBlock)) / atomSize;
349 }
350
351 inline MarkedBlock::Atom* MarkedBlock::atoms()
352 {
353     return reinterpret_cast<Atom*>(this);
354 }
355
356 inline bool MarkedBlock::isAtomAligned(const void* p)
357 {
358     return !(reinterpret_cast<Bits>(p) & atomAlignmentMask);
359 }
360
361 inline void* MarkedBlock::Handle::cellAlign(void* p)
362 {
363     Bits base = reinterpret_cast<Bits>(block().atoms() + firstAtom());
364     Bits bits = reinterpret_cast<Bits>(p);
365     bits -= base;
366     bits -= bits % cellSize();
367     bits += base;
368     return reinterpret_cast<void*>(bits);
369 }
370
371 inline MarkedBlock* MarkedBlock::blockFor(const void* p)
372 {
373     return reinterpret_cast<MarkedBlock*>(reinterpret_cast<Bits>(p) & blockMask);
374 }
375
376 inline MarkedAllocator* MarkedBlock::Handle::allocator() const
377 {
378     return m_allocator;
379 }
380
381 inline Heap* MarkedBlock::Handle::heap() const
382 {
383     return m_weakSet.heap();
384 }
385
386 inline VM* MarkedBlock::Handle::vm() const
387 {
388     return m_weakSet.vm();
389 }
390
391 inline VM* MarkedBlock::vm() const
392 {
393     return m_vm;
394 }
395
396 inline WeakSet& MarkedBlock::Handle::weakSet()
397 {
398     return m_weakSet;
399 }
400
401 inline WeakSet& MarkedBlock::weakSet()
402 {
403     return m_handle.weakSet();
404 }
405
406 inline void MarkedBlock::Handle::shrink()
407 {
408     m_weakSet.shrink();
409 }
410
411 inline unsigned MarkedBlock::Handle::visitWeakSet(HeapRootVisitor& heapRootVisitor)
412 {
413     return m_weakSet.visit(heapRootVisitor);
414 }
415
416 inline void MarkedBlock::Handle::reapWeakSet()
417 {
418     m_weakSet.reap();
419 }
420
421 inline size_t MarkedBlock::Handle::cellSize()
422 {
423     return m_atomsPerCell * atomSize;
424 }
425
426 inline size_t MarkedBlock::cellSize()
427 {
428     return m_handle.cellSize();
429 }
430
431 inline const AllocatorAttributes& MarkedBlock::Handle::attributes() const
432 {
433     return m_attributes;
434 }
435
436 inline const AllocatorAttributes& MarkedBlock::attributes() const
437 {
438     return m_handle.attributes();
439 }
440
441 inline bool MarkedBlock::Handle::needsDestruction() const
442 {
443     return m_attributes.destruction == NeedsDestruction;
444 }
445
446 inline DestructionMode MarkedBlock::Handle::destruction() const
447 {
448     return m_attributes.destruction;
449 }
450
451 inline HeapCell::Kind MarkedBlock::Handle::cellKind() const
452 {
453     return m_attributes.cellKind;
454 }
455
456 inline size_t MarkedBlock::Handle::markCount()
457 {
458     return m_block->markCount();
459 }
460
461 inline size_t MarkedBlock::Handle::size()
462 {
463     return markCount() * cellSize();
464 }
465
466 inline size_t MarkedBlock::atomNumber(const void* p)
467 {
468     return (reinterpret_cast<Bits>(p) - reinterpret_cast<Bits>(this)) / atomSize;
469 }
470
471 inline bool MarkedBlock::areMarksStale(HeapVersion markingVersion)
472 {
473     return markingVersion != m_markingVersion;
474 }
475
476 ALWAYS_INLINE MarkedBlock::MarksWithDependency MarkedBlock::areMarksStaleWithDependency(HeapVersion markingVersion)
477 {
478     auto consumed = consumeLoad(&m_markingVersion);
479     MarksWithDependency ret;
480     ret.areStale = consumed.value != markingVersion;
481     ret.dependency = consumed.dependency;
482     return ret;
483 }
484
485 inline void MarkedBlock::aboutToMark(HeapVersion markingVersion)
486 {
487     if (UNLIKELY(areMarksStale(markingVersion)))
488         aboutToMarkSlow(markingVersion);
489     WTF::loadLoadFence();
490 }
491
492 #if ASSERT_DISABLED
493 inline void MarkedBlock::assertMarksNotStale()
494 {
495 }
496 #endif // ASSERT_DISABLED
497
498 inline void MarkedBlock::Handle::assertMarksNotStale()
499 {
500     block().assertMarksNotStale();
501 }
502
503 inline bool MarkedBlock::isMarked(HeapVersion markingVersion, const void* p)
504 {
505     return areMarksStale(markingVersion) ? false : m_marks.get(atomNumber(p));
506 }
507
508 inline bool MarkedBlock::isMarkedConcurrently(HeapVersion markingVersion, const void* p)
509 {
510     auto marksWithDependency = areMarksStaleWithDependency(markingVersion);
511     if (marksWithDependency.areStale)
512         return false;
513     return m_marks.get(atomNumber(p) + marksWithDependency.dependency);
514 }
515
516 inline bool MarkedBlock::testAndSetMarked(const void* p)
517 {
518     assertMarksNotStale();
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::isAtom(const void* p)
547 {
548     ASSERT(MarkedBlock::isAtomAligned(p));
549     size_t atomNumber = this->atomNumber(p);
550     size_t firstAtom = MarkedBlock::firstAtom();
551     if (atomNumber < firstAtom) // Filters pointers into MarkedBlock metadata.
552         return false;
553     if ((atomNumber - firstAtom) % m_handle.m_atomsPerCell) // Filters pointers into cell middles.
554         return false;
555     if (atomNumber >= m_handle.m_endAtom) // Filters pointers into invalid cells out of the range.
556         return false;
557     return true;
558 }
559
560 template <typename Functor>
561 inline IterationStatus MarkedBlock::Handle::forEachCell(const Functor& functor)
562 {
563     HeapCell::Kind kind = m_attributes.cellKind;
564     for (size_t i = firstAtom(); i < m_endAtom; i += m_atomsPerCell) {
565         HeapCell* cell = reinterpret_cast_ptr<HeapCell*>(&m_block->atoms()[i]);
566         if (functor(cell, kind) == IterationStatus::Done)
567             return IterationStatus::Done;
568     }
569     return IterationStatus::Continue;
570 }
571
572 inline bool MarkedBlock::hasAnyMarked() const
573 {
574     return m_biasedMarkCount != m_markCountBias;
575 }
576
577 inline void MarkedBlock::noteMarked()
578 {
579     // This is racy by design. We don't want to pay the price of an atomic increment!
580     int16_t biasedMarkCount = m_biasedMarkCount;
581     ++biasedMarkCount;
582     m_biasedMarkCount = biasedMarkCount;
583     if (UNLIKELY(!biasedMarkCount))
584         noteMarkedSlow();
585 }
586
587 } // namespace JSC
588
589 namespace WTF {
590
591 struct MarkedBlockHash : PtrHash<JSC::MarkedBlock*> {
592     static unsigned hash(JSC::MarkedBlock* const& key)
593     {
594         // Aligned VM regions tend to be monotonically increasing integers,
595         // which is a great hash function, but we have to remove the low bits,
596         // since they're always zero, which is a terrible hash function!
597         return reinterpret_cast<JSC::Bits>(key) / JSC::MarkedBlock::blockSize;
598     }
599 };
600
601 template<> struct DefaultHash<JSC::MarkedBlock*> {
602     typedef MarkedBlockHash Hash;
603 };
604
605 void printInternal(PrintStream& out, JSC::MarkedBlock::Handle::SweepMode);
606
607 } // namespace WTF