1/*
2 * Copyright (C) 2019 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 <array>
29#include <wtf/FastBitVector.h>
30#include <wtf/Vector.h>
31
32namespace JSC {
33
34#define FOR_EACH_BLOCK_DIRECTORY_BIT(macro) \
35 macro(live, Live) /* The set of block indices that have actual blocks. */\
36 macro(empty, Empty) /* The set of all blocks that have no live objects. */ \
37 macro(allocated, Allocated) /* The set of all blocks that are full of live objects. */\
38 macro(canAllocateButNotEmpty, CanAllocateButNotEmpty) /* The set of all blocks are neither empty nor retired (i.e. are more than minMarkedBlockUtilization full). */ \
39 macro(destructible, Destructible) /* The set of all blocks that may have destructors to run. */\
40 macro(eden, Eden) /* The set of all blocks that have new objects since the last GC. */\
41 macro(unswept, Unswept) /* The set of all blocks that could be swept by the incremental sweeper. */\
42 \
43 /* These are computed during marking. */\
44 macro(markingNotEmpty, MarkingNotEmpty) /* The set of all blocks that are not empty. */ \
45 macro(markingRetired, MarkingRetired) /* The set of all blocks that are retired. */
46
47// FIXME: We defined canAllocateButNotEmpty and empty to be exclusive:
48//
49// canAllocateButNotEmpty & empty == 0
50//
51// Instead of calling it canAllocate and making it inclusive:
52//
53// canAllocate & empty == empty
54//
55// The latter is probably better. I'll leave it to a future bug to fix that, since breathing on
56// this code leads to regressions for days, and it's not clear that making this change would
57// improve perf since it would not change the collector's behavior, and either way the directory
58// has to look at both bitvectors.
59// https://bugs.webkit.org/show_bug.cgi?id=162121
60
61class BlockDirectoryBits {
62 WTF_MAKE_FAST_ALLOCATED;
63public:
64 static constexpr unsigned bitsPerSegment = 32;
65 static constexpr unsigned segmentShift = 5;
66 static constexpr unsigned indexMask = (1U << segmentShift) - 1;
67 static_assert((1 << segmentShift) == bitsPerSegment);
68
69#define BLOCK_DIRECTORY_BIT_KIND_COUNT(lowerBitName, capitalBitName) + 1
70 static constexpr unsigned numberOfBlockDirectoryBitKinds = 0 FOR_EACH_BLOCK_DIRECTORY_BIT(BLOCK_DIRECTORY_BIT_KIND_COUNT);
71#undef BLOCK_DIRECTORY_BIT_KIND_COUNT
72
73 enum class Kind {
74#define BLOCK_DIRECTORY_BIT_KIND_DECLARATION(lowerBitName, capitalBitName) \
75 capitalBitName,
76 FOR_EACH_BLOCK_DIRECTORY_BIT(BLOCK_DIRECTORY_BIT_KIND_DECLARATION)
77#undef BLOCK_DIRECTORY_BIT_KIND_DECLARATION
78 };
79
80 class Segment {
81 public:
82 Segment() = default;
83 std::array<uint32_t, numberOfBlockDirectoryBitKinds> m_data { };
84 };
85
86 template<Kind kind>
87 class BlockDirectoryBitVectorWordView {
88 WTF_MAKE_FAST_ALLOCATED;
89 public:
90 using ViewType = BlockDirectoryBitVectorWordView;
91
92 BlockDirectoryBitVectorWordView() = default;
93
94 BlockDirectoryBitVectorWordView(const Segment* segments, size_t numBits)
95 : m_segments(segments)
96 , m_numBits(numBits)
97 {
98 }
99
100 size_t numBits() const
101 {
102 return m_numBits;
103 }
104
105 uint32_t word(size_t index) const
106 {
107 ASSERT(index < WTF::fastBitVectorArrayLength(numBits()));
108 return m_segments[index].m_data[static_cast<unsigned>(kind)];
109 }
110
111 uint32_t& word(size_t index)
112 {
113 ASSERT(index < WTF::fastBitVectorArrayLength(numBits()));
114 return const_cast<Segment*>(m_segments)[index].m_data[static_cast<unsigned>(kind)];
115 }
116
117 void clearAll()
118 {
119 for (size_t index = 0; index < WTF::fastBitVectorArrayLength(numBits()); ++index)
120 const_cast<Segment*>(m_segments)[index].m_data[static_cast<unsigned>(kind)] = 0;
121 }
122
123 BlockDirectoryBitVectorWordView view() const { return *this; }
124
125 private:
126 const Segment* m_segments { nullptr };
127 size_t m_numBits { 0 };
128 };
129
130 template<Kind kind>
131 using BlockDirectoryBitVectorView = WTF::FastBitVectorImpl<BlockDirectoryBitVectorWordView<kind>>;
132
133 template<Kind kind>
134 class BlockDirectoryBitVectorRef final : public BlockDirectoryBitVectorView<kind> {
135 public:
136 using Base = BlockDirectoryBitVectorView<kind>;
137
138 explicit BlockDirectoryBitVectorRef(BlockDirectoryBitVectorWordView<kind> view)
139 : Base(view)
140 {
141 }
142
143 template<typename OtherWords>
144 BlockDirectoryBitVectorRef& operator=(const WTF::FastBitVectorImpl<OtherWords>& other)
145 {
146 ASSERT(Base::numBits() == other.numBits());
147 for (unsigned i = Base::arrayLength(); i--;)
148 Base::unsafeWords().word(i) = other.unsafeWords().word(i);
149 return *this;
150 }
151
152 template<typename OtherWords>
153 BlockDirectoryBitVectorRef& operator|=(const WTF::FastBitVectorImpl<OtherWords>& other)
154 {
155 ASSERT(Base::numBits() == other.numBits());
156 for (unsigned i = Base::arrayLength(); i--;)
157 Base::unsafeWords().word(i) |= other.unsafeWords().word(i);
158 return *this;
159 }
160
161 void clearAll()
162 {
163 Base::unsafeWords().clearAll();
164 }
165
166 WTF::FastBitReference at(size_t index)
167 {
168 ASSERT(index < Base::numBits());
169 return WTF::FastBitReference(&Base::unsafeWords().word(index >> 5), 1 << (index & 31));
170 }
171
172 WTF::FastBitReference operator[](size_t index)
173 {
174 return at(index);
175 }
176 };
177
178#define BLOCK_DIRECTORY_BIT_ACCESSORS(lowerBitName, capitalBitName) \
179 bool is ## capitalBitName(size_t index) const \
180 { \
181 return lowerBitName()[index]; \
182 } \
183 void setIs ## capitalBitName(size_t index, bool value) \
184 { \
185 lowerBitName()[index] = value; \
186 } \
187 BlockDirectoryBitVectorView<Kind::capitalBitName> lowerBitName() const \
188 { \
189 return BlockDirectoryBitVectorView<Kind::capitalBitName>(BlockDirectoryBitVectorWordView<Kind::capitalBitName>(m_segments.data(), m_numBits)); \
190 } \
191 BlockDirectoryBitVectorRef<Kind::capitalBitName> lowerBitName() \
192 { \
193 return BlockDirectoryBitVectorRef<Kind::capitalBitName>(BlockDirectoryBitVectorWordView<Kind::capitalBitName>(m_segments.data(), m_numBits)); \
194 }
195 FOR_EACH_BLOCK_DIRECTORY_BIT(BLOCK_DIRECTORY_BIT_ACCESSORS)
196#undef BLOCK_DIRECTORY_BIT_ACCESSORS
197
198 unsigned numBits() const { return m_numBits; }
199
200 void resize(unsigned numBits)
201 {
202 unsigned oldNumBits = m_numBits;
203 m_numBits = numBits;
204 m_segments.resize(WTF::fastBitVectorArrayLength(numBits));
205 unsigned usedBitsInLastSegment = numBits & indexMask; // This is 0 if all bits are used.
206 if (numBits < oldNumBits && usedBitsInLastSegment) {
207 // Clear the last segment.
208 ASSERT(usedBitsInLastSegment < bitsPerSegment);
209 auto& segment = m_segments.last();
210 uint32_t mask = (1U << usedBitsInLastSegment) - 1;
211 for (unsigned index = 0; index < numberOfBlockDirectoryBitKinds; ++index)
212 segment.m_data[index] &= mask;
213 }
214 }
215
216 template<typename Func>
217 void forEachSegment(const Func& func)
218 {
219 unsigned index = 0;
220 for (auto& segment : m_segments)
221 func(index++, segment);
222 }
223
224private:
225 Vector<Segment> m_segments;
226 unsigned m_numBits { 0 };
227};
228
229} // namespace JSC
230