c169d9df55f0d52a7be374b02fd03112c910ddb2
[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/Vector.h>
35
36 namespace JSC {
37
38 class GCDeferralContext;
39 class Heap;
40 class MarkedSpace;
41 class LLIntOffsetsExtractor;
42
43 #define FOR_EACH_MARKED_ALLOCATOR_BIT(macro) \
44     macro(live, Live) /* The set of block indices that have actual blocks. */\
45     macro(empty, Empty) /* The set of all blocks that have no live objects. */ \
46     macro(allocated, Allocated) /* The set of all blocks that are full of live objects. */\
47     macro(canAllocateButNotEmpty, CanAllocateButNotEmpty) /* The set of all blocks are neither empty nor retired (i.e. are more than minMarkedBlockUtilization full). */ \
48     macro(destructible, Destructible) /* The set of all blocks that may have destructors to run. */\
49     macro(eden, Eden) /* The set of all blocks that have new objects since the last GC. */\
50     macro(unswept, Unswept) /* The set of all blocks that could be swept by the incremental sweeper. */\
51     \
52     /* These are computed during marking. */\
53     macro(markingNotEmpty, MarkingNotEmpty) /* The set of all blocks that are not empty. */ \
54     macro(markingRetired, MarkingRetired) /* The set of all blocks that are retired. */
55
56 // FIXME: We defined canAllocateButNotEmpty and empty to be exclusive:
57 //
58 //     canAllocateButNotEmpty & empty == 0
59 //
60 // Instead of calling it canAllocate and making it inclusive:
61 //
62 //     canAllocate & empty == empty
63 //
64 // The latter is probably better. I'll leave it to a future bug to fix that, since breathing on
65 // this code leads to regressions for days, and it's not clear that making this change would
66 // improve perf since it would not change the collector's behavior, and either way the allocator
67 // has to look at both bitvectors.
68 // https://bugs.webkit.org/show_bug.cgi?id=162121
69
70 class MarkedAllocator {
71     WTF_MAKE_NONCOPYABLE(MarkedAllocator);
72     WTF_MAKE_FAST_ALLOCATED;
73     
74     friend class LLIntOffsetsExtractor;
75
76 public:
77     static ptrdiff_t offsetOfFreeList();
78     static ptrdiff_t offsetOfCellSize();
79
80     MarkedAllocator(Heap*, size_t cellSize);
81     void setSubspace(Subspace*);
82     void lastChanceToFinalize();
83     void prepareForAllocation();
84     void stopAllocating();
85     void resumeAllocating();
86     void beginMarkingForFullCollection();
87     void endMarking();
88     void snapshotUnsweptForEdenCollection();
89     void snapshotUnsweptForFullCollection();
90     void sweep();
91     void shrink();
92     void assertNoUnswept();
93     size_t cellSize() const { return m_cellSize; }
94     const AllocatorAttributes& attributes() const { return m_attributes; }
95     bool needsDestruction() const { return m_attributes.destruction == NeedsDestruction; }
96     DestructionMode destruction() const { return m_attributes.destruction; }
97     HeapCell::Kind cellKind() const { return m_attributes.cellKind; }
98     void* allocate(GCDeferralContext*, AllocationFailureMode);
99     Heap* heap() { return m_heap; }
100
101     bool isFreeListedCell(const void* target) const;
102
103     template<typename Functor> void forEachBlock(const Functor&);
104     template<typename Functor> void forEachNotEmptyBlock(const Functor&);
105     
106     void addBlock(MarkedBlock::Handle*);
107     void removeBlock(MarkedBlock::Handle*);
108
109     bool isPagedOut(double deadline);
110     
111     static size_t blockSizeForBytes(size_t);
112     
113     Lock& bitvectorLock() { return m_bitvectorLock; }
114    
115 #define MARKED_ALLOCATOR_BIT_ACCESSORS(lowerBitName, capitalBitName)     \
116     bool is ## capitalBitName(const AbstractLocker&, size_t index) const { return m_ ## lowerBitName[index]; } \
117     bool is ## capitalBitName(const AbstractLocker& locker, MarkedBlock::Handle* block) const { return is ## capitalBitName(locker, block->index()); } \
118     void setIs ## capitalBitName(const AbstractLocker&, size_t index, bool value) { m_ ## lowerBitName[index] = value; } \
119     void setIs ## capitalBitName(const AbstractLocker& locker, MarkedBlock::Handle* block, bool value) { setIs ## capitalBitName(locker, block->index(), value); }
120     FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_ACCESSORS)
121 #undef MARKED_ALLOCATOR_BIT_ACCESSORS
122
123     template<typename Func>
124     void forEachBitVector(const AbstractLocker&, const Func& func)
125     {
126 #define MARKED_ALLOCATOR_BIT_CALLBACK(lowerBitName, capitalBitName) \
127         func(m_ ## lowerBitName);
128         FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_CALLBACK);
129 #undef MARKED_ALLOCATOR_BIT_CALLBACK
130     }
131     
132     template<typename Func>
133     void forEachBitVectorWithName(const AbstractLocker&, const Func& func)
134     {
135 #define MARKED_ALLOCATOR_BIT_CALLBACK(lowerBitName, capitalBitName) \
136         func(m_ ## lowerBitName, #capitalBitName);
137         FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_CALLBACK);
138 #undef MARKED_ALLOCATOR_BIT_CALLBACK
139     }
140     
141     MarkedAllocator* nextAllocator() const { return m_nextAllocator; }
142     MarkedAllocator* nextAllocatorInSubspace() const { return m_nextAllocatorInSubspace; }
143     MarkedAllocator* nextAllocatorInAlignedMemoryAllocator() const { return m_nextAllocatorInAlignedMemoryAllocator; }
144     
145     void setNextAllocator(MarkedAllocator* allocator) { m_nextAllocator = allocator; }
146     void setNextAllocatorInSubspace(MarkedAllocator* allocator) { m_nextAllocatorInSubspace = allocator; }
147     void setNextAllocatorInAlignedMemoryAllocator(MarkedAllocator* allocator) { m_nextAllocatorInAlignedMemoryAllocator = allocator; }
148     
149     MarkedBlock::Handle* findEmptyBlockToSteal();
150     
151     MarkedBlock::Handle* findBlockToSweep();
152     
153     Subspace* subspace() const { return m_subspace; }
154     MarkedSpace& markedSpace() const;
155     
156     const FreeList& freeList() const { return m_freeList; }
157     
158     void dump(PrintStream&) const;
159     void dumpBits(PrintStream& = WTF::dataFile());
160     
161 private:
162     friend class MarkedBlock;
163     
164     JS_EXPORT_PRIVATE void* allocateSlowCase(GCDeferralContext*, AllocationFailureMode failureMode);
165     void didConsumeFreeList();
166     void* tryAllocateWithoutCollecting();
167     MarkedBlock::Handle* tryAllocateBlock();
168     void* tryAllocateIn(MarkedBlock::Handle*);
169     void* allocateIn(MarkedBlock::Handle*);
170     ALWAYS_INLINE void doTestCollectionsIfNeeded(GCDeferralContext*);
171     
172     FreeList m_freeList;
173     
174     Vector<MarkedBlock::Handle*> m_blocks;
175     Vector<unsigned> m_freeBlockIndices;
176
177     // Mutator uses this to guard resizing the bitvectors. Those things in the GC that may run
178     // concurrently to the mutator must lock this when accessing the bitvectors.
179     Lock m_bitvectorLock;
180 #define MARKED_ALLOCATOR_BIT_DECLARATION(lowerBitName, capitalBitName) \
181     FastBitVector m_ ## lowerBitName;
182     FOR_EACH_MARKED_ALLOCATOR_BIT(MARKED_ALLOCATOR_BIT_DECLARATION)
183 #undef MARKED_ALLOCATOR_BIT_DECLARATION
184     
185     // After you do something to a block based on one of these cursors, you clear the bit in the
186     // corresponding bitvector and leave the cursor where it was.
187     size_t m_allocationCursor { 0 }; // Points to the next block that is a candidate for allocation.
188     size_t m_emptyCursor { 0 }; // Points to the next block that is a candidate for empty allocation (allocating in empty blocks).
189     size_t m_unsweptCursor { 0 }; // Points to the next block that is a candidate for incremental sweeping.
190     
191     MarkedBlock::Handle* m_currentBlock;
192     MarkedBlock::Handle* m_lastActiveBlock;
193
194     Lock m_lock;
195     unsigned m_cellSize;
196     AllocatorAttributes m_attributes;
197     // FIXME: All of these should probably be references.
198     // https://bugs.webkit.org/show_bug.cgi?id=166988
199     Heap* m_heap { nullptr };
200     Subspace* m_subspace { nullptr };
201     MarkedAllocator* m_nextAllocator { nullptr };
202     MarkedAllocator* m_nextAllocatorInSubspace { nullptr };
203     MarkedAllocator* m_nextAllocatorInAlignedMemoryAllocator { nullptr };
204 };
205
206 inline ptrdiff_t MarkedAllocator::offsetOfFreeList()
207 {
208     return OBJECT_OFFSETOF(MarkedAllocator, m_freeList);
209 }
210
211 inline ptrdiff_t MarkedAllocator::offsetOfCellSize()
212 {
213     return OBJECT_OFFSETOF(MarkedAllocator, m_cellSize);
214 }
215
216 } // namespace JSC