GC constraint solving should be parallel
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkedAllocator.h
1 /*
2  * Copyright (C) 2012-2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #pragma once
27
28 #include "AllocationFailureMode.h"
29 #include "AllocatorAttributes.h"
30 #include "FreeList.h"
31 #include "MarkedBlock.h"
32 #include <wtf/DataLog.h>
33 #include <wtf/FastBitVector.h>
34 #include <wtf/SharedTask.h>
35 #include <wtf/Vector.h>
36
37 namespace JSC {
38
39 class GCDeferralContext;
40 class Heap;
41 class MarkedSpace;
42 class LLIntOffsetsExtractor;
43
44 #define FOR_EACH_MARKED_ALLOCATOR_BIT(macro) \
45     macro(live, Live) /* The set of block indices that have actual blocks. */\
46     macro(empty, Empty) /* The set of all blocks that have no live objects. */ \
47     macro(allocated, Allocated) /* The set of all blocks that are full of live objects. */\
48     macro(canAllocateButNotEmpty, CanAllocateButNotEmpty) /* The set of all blocks are neither empty nor retired (i.e. are more than minMarkedBlockUtilization full). */ \
49     macro(destructible, Destructible) /* The set of all blocks that may have destructors to run. */\
50     macro(eden, Eden) /* The set of all blocks that have new objects since the last GC. */\
51     macro(unswept, Unswept) /* The set of all blocks that could be swept by the incremental sweeper. */\
52     \
53     /* These are computed during marking. */\
54     macro(markingNotEmpty, MarkingNotEmpty) /* The set of all blocks that are not empty. */ \
55     macro(markingRetired, MarkingRetired) /* The set of all blocks that are retired. */
56
57 // FIXME: We defined canAllocateButNotEmpty and empty to be exclusive:
58 //
59 //     canAllocateButNotEmpty & empty == 0
60 //
61 // Instead of calling it canAllocate and making it inclusive:
62 //
63 //     canAllocate & empty == empty
64 //
65 // The latter is probably better. I'll leave it to a future bug to fix that, since breathing on
66 // this code leads to regressions for days, and it's not clear that making this change would
67 // improve perf since it would not change the collector's behavior, and either way the allocator
68 // has to look at both bitvectors.
69 // https://bugs.webkit.org/show_bug.cgi?id=162121
70
71 class MarkedAllocator {
72     WTF_MAKE_NONCOPYABLE(MarkedAllocator);
73     WTF_MAKE_FAST_ALLOCATED;
74     
75     friend class LLIntOffsetsExtractor;
76
77 public:
78     static ptrdiff_t offsetOfFreeList();
79     static ptrdiff_t offsetOfCellSize();
80
81     MarkedAllocator(Heap*, size_t cellSize);
82     void setSubspace(Subspace*);
83     void lastChanceToFinalize();
84     void prepareForAllocation();
85     void stopAllocating();
86     void resumeAllocating();
87     void beginMarkingForFullCollection();
88     void endMarking();
89     void snapshotUnsweptForEdenCollection();
90     void snapshotUnsweptForFullCollection();
91     void sweep();
92     void shrink();
93     void assertNoUnswept();
94     size_t cellSize() const { return m_cellSize; }
95     const AllocatorAttributes& attributes() const { return m_attributes; }
96     bool needsDestruction() const { return m_attributes.destruction == NeedsDestruction; }
97     DestructionMode destruction() const { return m_attributes.destruction; }
98     HeapCell::Kind cellKind() const { return m_attributes.cellKind; }
99     void* allocate(GCDeferralContext*, AllocationFailureMode);
100     Heap* heap() { return m_heap; }
101
102     bool isFreeListedCell(const void* target) const;
103
104     template<typename Functor> void forEachBlock(const Functor&);
105     template<typename Functor> void forEachNotEmptyBlock(const Functor&);
106     
107     RefPtr<SharedTask<MarkedBlock::Handle*()>> parallelNotEmptyBlockSource();
108     
109     void addBlock(MarkedBlock::Handle*);
110     void removeBlock(MarkedBlock::Handle*);
111
112     bool isPagedOut(double deadline);
113     
114     static size_t blockSizeForBytes(size_t);
115     
116     Lock& bitvectorLock() { return m_bitvectorLock; }
117    
118 #define MARKED_ALLOCATOR_BIT_ACCESSORS(lowerBitName, capitalBitName)     \
119     bool is ## capitalBitName(const AbstractLocker&, size_t index) const { return m_ ## lowerBitName[index]; } \
120     bool is ## capitalBitName(const AbstractLocker& locker, MarkedBlock::Handle* block) const { return is ## capitalBitName(locker, block->index()); } \
121     void setIs ## capitalBitName(const AbstractLocker&, size_t index, bool value) { m_ ## lowerBitName[index] = value; } \
122     void setIs ## capitalBitName(const AbstractLocker& locker, MarkedBlock::Handle* block, bool value) { setIs ## capitalBitName(locker, block->index(), value); }
123     FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_ACCESSORS)
124 #undef MARKED_ALLOCATOR_BIT_ACCESSORS
125
126     template<typename Func>
127     void forEachBitVector(const AbstractLocker&, const Func& func)
128     {
129 #define MARKED_ALLOCATOR_BIT_CALLBACK(lowerBitName, capitalBitName) \
130         func(m_ ## lowerBitName);
131         FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_CALLBACK);
132 #undef MARKED_ALLOCATOR_BIT_CALLBACK
133     }
134     
135     template<typename Func>
136     void forEachBitVectorWithName(const AbstractLocker&, const Func& func)
137     {
138 #define MARKED_ALLOCATOR_BIT_CALLBACK(lowerBitName, capitalBitName) \
139         func(m_ ## lowerBitName, #capitalBitName);
140         FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_CALLBACK);
141 #undef MARKED_ALLOCATOR_BIT_CALLBACK
142     }
143     
144     MarkedAllocator* nextAllocator() const { return m_nextAllocator; }
145     MarkedAllocator* nextAllocatorInSubspace() const { return m_nextAllocatorInSubspace; }
146     MarkedAllocator* nextAllocatorInAlignedMemoryAllocator() const { return m_nextAllocatorInAlignedMemoryAllocator; }
147     
148     void setNextAllocator(MarkedAllocator* allocator) { m_nextAllocator = allocator; }
149     void setNextAllocatorInSubspace(MarkedAllocator* allocator) { m_nextAllocatorInSubspace = allocator; }
150     void setNextAllocatorInAlignedMemoryAllocator(MarkedAllocator* allocator) { m_nextAllocatorInAlignedMemoryAllocator = allocator; }
151     
152     MarkedBlock::Handle* findEmptyBlockToSteal();
153     
154     MarkedBlock::Handle* findBlockToSweep();
155     
156     Subspace* subspace() const { return m_subspace; }
157     MarkedSpace& markedSpace() const;
158     
159     const FreeList& freeList() const { return m_freeList; }
160     
161     void dump(PrintStream&) const;
162     void dumpBits(PrintStream& = WTF::dataFile());
163     
164 private:
165     friend class MarkedBlock;
166     
167     JS_EXPORT_PRIVATE void* allocateSlowCase(GCDeferralContext*, AllocationFailureMode failureMode);
168     void didConsumeFreeList();
169     void* tryAllocateWithoutCollecting();
170     MarkedBlock::Handle* tryAllocateBlock();
171     void* tryAllocateIn(MarkedBlock::Handle*);
172     void* allocateIn(MarkedBlock::Handle*);
173     ALWAYS_INLINE void doTestCollectionsIfNeeded(GCDeferralContext*);
174     
175     FreeList m_freeList;
176     
177     Vector<MarkedBlock::Handle*> m_blocks;
178     Vector<unsigned> m_freeBlockIndices;
179
180     // Mutator uses this to guard resizing the bitvectors. Those things in the GC that may run
181     // concurrently to the mutator must lock this when accessing the bitvectors.
182     Lock m_bitvectorLock;
183 #define MARKED_ALLOCATOR_BIT_DECLARATION(lowerBitName, capitalBitName) \
184     FastBitVector m_ ## lowerBitName;
185     FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_DECLARATION)
186 #undef MARKED_ALLOCATOR_BIT_DECLARATION
187     
188     // After you do something to a block based on one of these cursors, you clear the bit in the
189     // corresponding bitvector and leave the cursor where it was.
190     size_t m_allocationCursor { 0 }; // Points to the next block that is a candidate for allocation.
191     size_t m_emptyCursor { 0 }; // Points to the next block that is a candidate for empty allocation (allocating in empty blocks).
192     size_t m_unsweptCursor { 0 }; // Points to the next block that is a candidate for incremental sweeping.
193     
194     MarkedBlock::Handle* m_currentBlock;
195     MarkedBlock::Handle* m_lastActiveBlock;
196
197     Lock m_lock;
198     unsigned m_cellSize;
199     AllocatorAttributes m_attributes;
200     // FIXME: All of these should probably be references.
201     // https://bugs.webkit.org/show_bug.cgi?id=166988
202     Heap* m_heap { nullptr };
203     Subspace* m_subspace { nullptr };
204     MarkedAllocator* m_nextAllocator { nullptr };
205     MarkedAllocator* m_nextAllocatorInSubspace { nullptr };
206     MarkedAllocator* m_nextAllocatorInAlignedMemoryAllocator { nullptr };
207 };
208
209 inline ptrdiff_t MarkedAllocator::offsetOfFreeList()
210 {
211     return OBJECT_OFFSETOF(MarkedAllocator, m_freeList);
212 }
213
214 inline ptrdiff_t MarkedAllocator::offsetOfCellSize()
215 {
216     return OBJECT_OFFSETOF(MarkedAllocator, m_cellSize);
217 }
218
219 } // namespace JSC