1 //
2 // Copyright 2019 The ANGLE Project Authors. All rights reserved.
3 // Use of this source code is governed by a BSD-style license that can be
4 // found in the LICENSE file.
5 //
6 // serial_utils:
7 // Utilities for generating unique IDs for resources in ANGLE.
8 //
9
10 #ifndef LIBANGLE_RENDERER_SERIAL_UTILS_H_
11 #define LIBANGLE_RENDERER_SERIAL_UTILS_H_
12
13 #include <array>
14 #include <atomic>
15 #include <limits>
16
17 #include "common/angleutils.h"
18 #include "common/debug.h"
19
20 namespace rx
21 {
22 class ResourceSerial
23 {
24 public:
ResourceSerial()25 constexpr ResourceSerial() : mValue(kDirty) {}
ResourceSerial(uintptr_t value)26 explicit constexpr ResourceSerial(uintptr_t value) : mValue(value) {}
27 constexpr bool operator==(ResourceSerial other) const { return mValue == other.mValue; }
28 constexpr bool operator!=(ResourceSerial other) const { return mValue != other.mValue; }
29
dirty()30 void dirty() { mValue = kDirty; }
clear()31 void clear() { mValue = kEmpty; }
32
valid()33 constexpr bool valid() const { return mValue != kEmpty && mValue != kDirty; }
empty()34 constexpr bool empty() const { return mValue == kEmpty; }
35
36 private:
37 constexpr static uintptr_t kDirty = std::numeric_limits<uintptr_t>::max();
38 constexpr static uintptr_t kEmpty = 0;
39
40 uintptr_t mValue;
41 };
42
43 // Class UniqueSerial defines unique serial number for object identification. It has only
44 // equal/unequal comparison but no greater/smaller comparison. The default constructor creates an
45 // invalid value.
46 class UniqueSerial final
47 {
48 public:
UniqueSerial()49 constexpr UniqueSerial() : mValue(kInvalid) {}
50 constexpr UniqueSerial(const UniqueSerial &other) = default;
51 UniqueSerial &operator=(const UniqueSerial &other) = default;
52
53 constexpr bool operator==(const UniqueSerial &other) const
54 {
55 return mValue != kInvalid && mValue == other.mValue;
56 }
57 constexpr bool operator!=(const UniqueSerial &other) const
58 {
59 return mValue == kInvalid || mValue != other.mValue;
60 }
61
62 // Useful for serialization.
getValue()63 constexpr uint64_t getValue() const { return mValue; }
valid()64 constexpr bool valid() const { return mValue != kInvalid; }
65
66 private:
67 friend class UniqueSerialFactory;
UniqueSerial(uint64_t value)68 constexpr explicit UniqueSerial(uint64_t value) : mValue(value) {}
69 uint64_t mValue;
70 static constexpr uint64_t kInvalid = 0;
71 };
72
73 class UniqueSerialFactory final : angle::NonCopyable
74 {
75 public:
UniqueSerialFactory()76 UniqueSerialFactory() : mSerial(1) {}
77
generate()78 UniqueSerial generate()
79 {
80 uint64_t current = mSerial++;
81 ASSERT(mSerial > current); // Integer overflow
82 return UniqueSerial(current);
83 }
84
85 private:
86 uint64_t mSerial;
87 };
88
89 // Class Serial defines a monotonically increasing serial number that indicates the timeline of
90 // execution.
91 class Serial final
92 {
93 public:
Serial()94 constexpr Serial() : mValue(0) {}
95 constexpr Serial(const Serial &other) = default;
96 Serial &operator=(const Serial &other) = default;
97
Infinite()98 static constexpr Serial Infinite() { return Serial(std::numeric_limits<uint64_t>::max()); }
99
100 constexpr bool operator==(const Serial &other) const { return mValue == other.mValue; }
101 constexpr bool operator!=(const Serial &other) const { return mValue != other.mValue; }
102 constexpr bool operator>(const Serial &other) const { return mValue > other.mValue; }
103 constexpr bool operator>=(const Serial &other) const { return mValue >= other.mValue; }
104 constexpr bool operator<(const Serial &other) const { return mValue < other.mValue; }
105 constexpr bool operator<=(const Serial &other) const { return mValue <= other.mValue; }
106
107 // Useful for serialization.
getValue()108 constexpr uint64_t getValue() const { return mValue; }
109
110 private:
111 friend class AtomicSerialFactory;
112 friend class RangedSerialFactory;
113 friend class AtomicQueueSerial;
Serial(uint64_t value)114 constexpr explicit Serial(uint64_t value) : mValue(value) {}
115 uint64_t mValue;
116 };
117
118 // Defines class to track the queue serial that can be load/store from multiple threads atomically.
119 class AtomicQueueSerial final
120 {
121 public:
122 AtomicQueueSerial &operator=(const Serial &other)
123 {
124 mValue.store(other.mValue, std::memory_order_release);
125 return *this;
126 }
getSerial()127 Serial getSerial() const { return Serial(mValue.load(std::memory_order_consume)); }
128
129 private:
130 static constexpr uint64_t kInvalid = 0;
131 std::atomic<uint64_t> mValue = kInvalid;
132 static_assert(decltype(mValue)::is_always_lock_free, "Must always be lock free");
133 };
134
135 // Used as default/initial serial
136 static constexpr Serial kZeroSerial = Serial();
137
138 // The factory to generate a serial number within the range [mSerial, mSerial+mCount}
139 class RangedSerialFactory final : angle::NonCopyable
140 {
141 public:
RangedSerialFactory()142 RangedSerialFactory() : mSerial(0), mCount(0) {}
143
reset()144 void reset() { mCount = 0; }
empty()145 bool empty() const { return mCount == 0; }
generate(Serial * serialOut)146 bool generate(Serial *serialOut)
147 {
148 if (mCount > 0)
149 {
150 uint64_t current = mSerial++;
151 ASSERT(mSerial > current); // Integer overflow
152 *serialOut = Serial(current);
153 mCount--;
154 return true;
155 }
156 return false;
157 }
158
159 private:
160 friend class AtomicSerialFactory;
initialize(uint64_t initialSerial,size_t count)161 void initialize(uint64_t initialSerial, size_t count)
162 {
163 mSerial = initialSerial;
164 mCount = count;
165 }
166 uint64_t mSerial;
167 size_t mCount;
168 };
169
170 class AtomicSerialFactory final : angle::NonCopyable
171 {
172 public:
AtomicSerialFactory()173 AtomicSerialFactory() : mSerial(1) {}
174
generate()175 Serial generate()
176 {
177 uint64_t current = mSerial++;
178 ASSERT(mSerial > current); // Integer overflow
179 return Serial(current);
180 }
181
reserve(RangedSerialFactory * rangeFactory,size_t count)182 void reserve(RangedSerialFactory *rangeFactory, size_t count)
183 {
184 uint64_t current = mSerial;
185 mSerial += count;
186 ASSERT(mSerial > current); // Integer overflow
187 rangeFactory->initialize(current, count);
188 }
189
190 private:
191 std::atomic<uint64_t> mSerial;
192 };
193
194 // For backend that supports multiple queue serials, QueueSerial includes a Serial and an index.
195 using SerialIndex = uint32_t;
196 static constexpr SerialIndex kInvalidQueueSerialIndex = SerialIndex(-1);
197
198 class QueueSerial;
199 // Because we release queue index when context becomes non-current, in order to use up all index
200 // count, you will need to have 256 threads each has a context current. This is not a reasonable
201 // usage case.
202 constexpr size_t kMaxQueueSerialIndexCount = 256;
203 // Fixed array of queue serials
204 class AtomicQueueSerialFixedArray final
205 {
206 public:
207 AtomicQueueSerialFixedArray() = default;
208 ~AtomicQueueSerialFixedArray() = default;
209
210 void setQueueSerial(SerialIndex index, Serial serial);
211 void setQueueSerial(const QueueSerial &queueSerial);
fill(Serial serial)212 void fill(Serial serial) { std::fill(mSerials.begin(), mSerials.end(), serial); }
213 Serial operator[](SerialIndex index) const { return mSerials[index].getSerial(); }
size()214 size_t size() const { return mSerials.size(); }
215
216 private:
217 std::array<AtomicQueueSerial, kMaxQueueSerialIndexCount> mSerials;
218 };
219 std::ostream &operator<<(std::ostream &os, const AtomicQueueSerialFixedArray &serials);
220
221 class QueueSerial final
222 {
223 public:
QueueSerial()224 QueueSerial() : mIndex(kInvalidQueueSerialIndex) {}
QueueSerial(SerialIndex index,Serial serial)225 QueueSerial(SerialIndex index, Serial serial) : mIndex(index), mSerial(serial)
226 {
227 ASSERT(index != kInvalidQueueSerialIndex);
228 }
229 constexpr QueueSerial(const QueueSerial &other) = default;
230 QueueSerial &operator=(const QueueSerial &other) = default;
231
232 constexpr bool operator==(const QueueSerial &other) const
233 {
234 return mIndex == other.mIndex && mSerial == other.mSerial;
235 }
236 constexpr bool operator!=(const QueueSerial &other) const
237 {
238 return mIndex != other.mIndex || mSerial != other.mSerial;
239 }
240 constexpr bool operator<(const QueueSerial &other) const
241 {
242 ASSERT(mIndex != kInvalidQueueSerialIndex);
243 ASSERT(mIndex == other.mIndex);
244 return mSerial < other.mSerial;
245 }
246 constexpr bool operator<=(const QueueSerial &other) const
247 {
248 ASSERT(mIndex != kInvalidQueueSerialIndex);
249 ASSERT(mIndex == other.mIndex);
250 return mSerial <= other.mSerial;
251 }
252 constexpr bool operator>(const QueueSerial &other) const
253 {
254 ASSERT(mIndex != kInvalidQueueSerialIndex);
255 ASSERT(mIndex == other.mIndex);
256 return mSerial > other.mSerial;
257 }
258 constexpr bool operator>=(const QueueSerial &other) const
259 {
260 ASSERT(mIndex != kInvalidQueueSerialIndex);
261 ASSERT(mIndex == other.mIndex);
262 return mSerial >= other.mSerial;
263 }
264
265 bool operator>(const AtomicQueueSerialFixedArray &serials) const
266 {
267 ASSERT(mIndex != kInvalidQueueSerialIndex);
268 return mSerial > serials[mIndex];
269 }
270 bool operator<=(const AtomicQueueSerialFixedArray &serials) const
271 {
272 ASSERT(mIndex != kInvalidQueueSerialIndex);
273 return mSerial <= serials[mIndex];
274 }
275
valid()276 constexpr bool valid() const { return mIndex != kInvalidQueueSerialIndex; }
277
getIndex()278 SerialIndex getIndex() const { return mIndex; }
getSerial()279 Serial getSerial() const { return mSerial; }
280
281 private:
282 SerialIndex mIndex;
283 Serial mSerial;
284 };
285 std::ostream &operator<<(std::ostream &os, const QueueSerial &queueSerial);
286
setQueueSerial(SerialIndex index,Serial serial)287 ANGLE_INLINE void AtomicQueueSerialFixedArray::setQueueSerial(SerialIndex index, Serial serial)
288 {
289 ASSERT(index != kInvalidQueueSerialIndex);
290 ASSERT(index < mSerials.size());
291 // Serial can only increase
292 ASSERT(serial > mSerials[index].getSerial());
293 mSerials[index] = serial;
294 }
295
setQueueSerial(const QueueSerial & queueSerial)296 ANGLE_INLINE void AtomicQueueSerialFixedArray::setQueueSerial(const QueueSerial &queueSerial)
297 {
298 setQueueSerial(queueSerial.getIndex(), queueSerial.getSerial());
299 }
300
301 ANGLE_INLINE std::ostream &operator<<(std::ostream &os, const AtomicQueueSerialFixedArray &serials)
302 {
303 // Search for last non-zero index (or 0 if all zeros).
304 SerialIndex lastIndex = serials.size() == 0 ? 0 : static_cast<SerialIndex>(serials.size() - 1);
305 while (lastIndex > 0 && serials[lastIndex].getValue() == 0)
306 {
307 lastIndex--;
308 }
309 os << '{';
310 for (SerialIndex i = 0; i < lastIndex; i++)
311 {
312 os << serials[i].getValue() << ',';
313 }
314 os << serials[lastIndex].getValue() << '}';
315 return os;
316 }
317
318 ANGLE_INLINE std::ostream &operator<<(std::ostream &os, const QueueSerial &queueSerial)
319 {
320 os << '{' << queueSerial.getIndex() << ':' << queueSerial.getSerial().getValue() << '}';
321 return os;
322 }
323 } // namespace rx
324
325 #endif // LIBANGLE_RENDERER_SERIAL_UTILS_H_
326