1/*
2 * Copyright (C) 2012-2018 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 "BlockDirectoryBits.h"
30#include "CellAttributes.h"
31#include "FreeList.h"
32#include "LocalAllocator.h"
33#include "MarkedBlock.h"
34#include <wtf/DataLog.h>
35#include <wtf/FastBitVector.h>
36#include <wtf/MonotonicTime.h>
37#include <wtf/SharedTask.h>
38#include <wtf/Vector.h>
39
40namespace JSC {
41
42class GCDeferralContext;
43class Heap;
44class IsoCellSet;
45class MarkedSpace;
46class LLIntOffsetsExtractor;
47
48class BlockDirectory {
49 WTF_MAKE_NONCOPYABLE(BlockDirectory);
50 WTF_MAKE_FAST_ALLOCATED;
51
52 friend class LLIntOffsetsExtractor;
53
54public:
55 BlockDirectory(size_t cellSize);
56 ~BlockDirectory();
57 void setSubspace(Subspace*);
58 void lastChanceToFinalize();
59 void prepareForAllocation();
60 void stopAllocating();
61 void stopAllocatingForGood();
62 void resumeAllocating();
63 void beginMarkingForFullCollection();
64 void endMarking();
65 void snapshotUnsweptForEdenCollection();
66 void snapshotUnsweptForFullCollection();
67 void sweep();
68 void shrink();
69 void assertNoUnswept();
70 size_t cellSize() const { return m_cellSize; }
71 const CellAttributes& attributes() const { return m_attributes; }
72 bool needsDestruction() const { return m_attributes.destruction == NeedsDestruction; }
73 DestructionMode destruction() const { return m_attributes.destruction; }
74 HeapCell::Kind cellKind() const { return m_attributes.cellKind; }
75
76 bool isFreeListedCell(const void* target);
77
78 template<typename Functor> void forEachBlock(const Functor&);
79 template<typename Functor> void forEachNotEmptyBlock(const Functor&);
80
81 RefPtr<SharedTask<MarkedBlock::Handle*()>> parallelNotEmptyBlockSource();
82
83 void addBlock(MarkedBlock::Handle*);
84 void removeBlock(MarkedBlock::Handle*);
85
86 bool isPagedOut(MonotonicTime deadline);
87
88 Lock& bitvectorLock() { return m_bitvectorLock; }
89
90#define BLOCK_DIRECTORY_BIT_ACCESSORS(lowerBitName, capitalBitName) \
91 bool is ## capitalBitName(const AbstractLocker&, size_t index) const { return m_bits.is ## capitalBitName(index); } \
92 bool is ## capitalBitName(const AbstractLocker& locker, MarkedBlock::Handle* block) const { return is ## capitalBitName(locker, block->index()); } \
93 void setIs ## capitalBitName(const AbstractLocker&, size_t index, bool value) { m_bits.setIs ## capitalBitName(index, value); } \
94 void setIs ## capitalBitName(const AbstractLocker& locker, MarkedBlock::Handle* block, bool value) { setIs ## capitalBitName(locker, block->index(), value); }
95 FOR_EACH_BLOCK_DIRECTORY_BIT(BLOCK_DIRECTORY_BIT_ACCESSORS)
96#undef BLOCK_DIRECTORY_BIT_ACCESSORS
97
98 template<typename Func>
99 void forEachBitVector(const AbstractLocker&, const Func& func)
100 {
101#define BLOCK_DIRECTORY_BIT_CALLBACK(lowerBitName, capitalBitName) \
102 func(m_bits.lowerBitName());
103 FOR_EACH_BLOCK_DIRECTORY_BIT(BLOCK_DIRECTORY_BIT_CALLBACK);
104#undef BLOCK_DIRECTORY_BIT_CALLBACK
105 }
106
107 template<typename Func>
108 void forEachBitVectorWithName(const AbstractLocker&, const Func& func)
109 {
110#define BLOCK_DIRECTORY_BIT_CALLBACK(lowerBitName, capitalBitName) \
111 func(m_bits.lowerBitName(), #capitalBitName);
112 FOR_EACH_BLOCK_DIRECTORY_BIT(BLOCK_DIRECTORY_BIT_CALLBACK);
113#undef BLOCK_DIRECTORY_BIT_CALLBACK
114 }
115
116 BlockDirectory* nextDirectory() const { return m_nextDirectory; }
117 BlockDirectory* nextDirectoryInSubspace() const { return m_nextDirectoryInSubspace; }
118 BlockDirectory* nextDirectoryInAlignedMemoryAllocator() const { return m_nextDirectoryInAlignedMemoryAllocator; }
119
120 void setNextDirectory(BlockDirectory* directory) { m_nextDirectory = directory; }
121 void setNextDirectoryInSubspace(BlockDirectory* directory) { m_nextDirectoryInSubspace = directory; }
122 void setNextDirectoryInAlignedMemoryAllocator(BlockDirectory* directory) { m_nextDirectoryInAlignedMemoryAllocator = directory; }
123
124 MarkedBlock::Handle* findEmptyBlockToSteal();
125
126 MarkedBlock::Handle* findBlockToSweep();
127
128 Subspace* subspace() const { return m_subspace; }
129 MarkedSpace& markedSpace() const;
130
131 void dump(PrintStream&) const;
132 void dumpBits(PrintStream& = WTF::dataFile());
133
134private:
135 friend class IsoCellSet;
136 friend class LocalAllocator;
137 friend class LocalSideAllocator;
138 friend class MarkedBlock;
139
140 MarkedBlock::Handle* findBlockForAllocation(LocalAllocator&);
141
142 MarkedBlock::Handle* tryAllocateBlock(Heap&);
143
144 Vector<MarkedBlock::Handle*> m_blocks;
145 Vector<unsigned> m_freeBlockIndices;
146
147 // Mutator uses this to guard resizing the bitvectors. Those things in the GC that may run
148 // concurrently to the mutator must lock this when accessing the bitvectors.
149 BlockDirectoryBits m_bits;
150 Lock m_bitvectorLock;
151 Lock m_localAllocatorsLock;
152 CellAttributes m_attributes;
153
154 unsigned m_cellSize;
155
156 // After you do something to a block based on one of these cursors, you clear the bit in the
157 // corresponding bitvector and leave the cursor where it was.
158 size_t m_emptyCursor { 0 };
159 size_t m_unsweptCursor { 0 }; // Points to the next block that is a candidate for incremental sweeping.
160
161 // FIXME: All of these should probably be references.
162 // https://bugs.webkit.org/show_bug.cgi?id=166988
163 Subspace* m_subspace { nullptr };
164 BlockDirectory* m_nextDirectory { nullptr };
165 BlockDirectory* m_nextDirectoryInSubspace { nullptr };
166 BlockDirectory* m_nextDirectoryInAlignedMemoryAllocator { nullptr };
167
168 SentinelLinkedList<LocalAllocator, BasicRawSentinelNode<LocalAllocator>> m_localAllocators;
169};
170
171} // namespace JSC
172