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