1 // Copyright 2020 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef V8_HEAP_BASE_WORKLIST_H_
6 #define V8_HEAP_BASE_WORKLIST_H_
7
8 #include <cstddef>
9 #include <utility>
10
11 #include "src/base/atomic-utils.h"
12 #include "src/base/logging.h"
13 #include "src/base/platform/mutex.h"
14 #include "testing/gtest/include/gtest/gtest_prod.h" // nogncheck
15
16 namespace heap {
17 namespace base {
18
19 namespace internal {
20 class V8_EXPORT_PRIVATE SegmentBase {
21 public:
22 static SegmentBase* GetSentinelSegmentAddress();
23
SegmentBase(uint16_t capacity)24 explicit SegmentBase(uint16_t capacity) : capacity_(capacity) {}
25
Size()26 size_t Size() const { return index_; }
IsEmpty()27 bool IsEmpty() const { return index_ == 0; }
IsFull()28 bool IsFull() const { return index_ == capacity_; }
Clear()29 void Clear() { index_ = 0; }
30
31 protected:
32 const uint16_t capacity_;
33 uint16_t index_ = 0;
34 };
35 } // namespace internal
36
37 // A global marking worklist that is similar the existing Worklist
38 // but does not reserve space and keep track of the local segments.
39 // Eventually this will replace Worklist after all its current uses
40 // are migrated.
41 template <typename EntryType, uint16_t SegmentSize>
42 class Worklist {
43 public:
44 static const int kSegmentSize = SegmentSize;
45 class Segment;
46 class Local;
47
48 Worklist() = default;
~Worklist()49 ~Worklist() { CHECK(IsEmpty()); }
50
51 void Push(Segment* segment);
52 bool Pop(Segment** segment);
53
54 // Returns true if the list of segments is empty.
55 bool IsEmpty();
56 // Returns the number of segments in the list.
57 size_t Size();
58
59 // Moves the segments of the given marking worklist into this
60 // marking worklist.
61 void Merge(Worklist<EntryType, SegmentSize>* other);
62
63 // These functions are not thread-safe. They should be called only
64 // if all local marking worklists that use the current worklist have
65 // been published and are empty.
66 void Clear();
67 template <typename Callback>
68 void Update(Callback callback);
69 template <typename Callback>
70 void Iterate(Callback callback);
71
72 private:
set_top(Segment * segment)73 void set_top(Segment* segment) {
74 v8::base::AsAtomicPtr(&top_)->store(segment, std::memory_order_relaxed);
75 }
76
77 v8::base::Mutex lock_;
78 Segment* top_ = nullptr;
79 std::atomic<size_t> size_{0};
80 };
81
82 template <typename EntryType, uint16_t SegmentSize>
Push(Segment * segment)83 void Worklist<EntryType, SegmentSize>::Push(Segment* segment) {
84 DCHECK(!segment->IsEmpty());
85 v8::base::MutexGuard guard(&lock_);
86 segment->set_next(top_);
87 set_top(segment);
88 size_.fetch_add(1, std::memory_order_relaxed);
89 }
90
91 template <typename EntryType, uint16_t SegmentSize>
Pop(Segment ** segment)92 bool Worklist<EntryType, SegmentSize>::Pop(Segment** segment) {
93 v8::base::MutexGuard guard(&lock_);
94 if (top_ == nullptr) return false;
95 DCHECK_LT(0U, size_);
96 size_.fetch_sub(1, std::memory_order_relaxed);
97 *segment = top_;
98 set_top(top_->next());
99 return true;
100 }
101
102 template <typename EntryType, uint16_t SegmentSize>
IsEmpty()103 bool Worklist<EntryType, SegmentSize>::IsEmpty() {
104 return v8::base::AsAtomicPtr(&top_)->load(std::memory_order_relaxed) ==
105 nullptr;
106 }
107
108 template <typename EntryType, uint16_t SegmentSize>
Size()109 size_t Worklist<EntryType, SegmentSize>::Size() {
110 // It is safe to read |size_| without a lock since this variable is
111 // atomic, keeping in mind that threads may not immediately see the new
112 // value when it is updated.
113 return size_.load(std::memory_order_relaxed);
114 }
115
116 template <typename EntryType, uint16_t SegmentSize>
Clear()117 void Worklist<EntryType, SegmentSize>::Clear() {
118 v8::base::MutexGuard guard(&lock_);
119 size_.store(0, std::memory_order_relaxed);
120 Segment* current = top_;
121 while (current != nullptr) {
122 Segment* tmp = current;
123 current = current->next();
124 delete tmp;
125 }
126 set_top(nullptr);
127 }
128
129 template <typename EntryType, uint16_t SegmentSize>
130 template <typename Callback>
Update(Callback callback)131 void Worklist<EntryType, SegmentSize>::Update(Callback callback) {
132 v8::base::MutexGuard guard(&lock_);
133 Segment* prev = nullptr;
134 Segment* current = top_;
135 size_t num_deleted = 0;
136 while (current != nullptr) {
137 current->Update(callback);
138 if (current->IsEmpty()) {
139 DCHECK_LT(0U, size_);
140 ++num_deleted;
141 if (prev == nullptr) {
142 top_ = current->next();
143 } else {
144 prev->set_next(current->next());
145 }
146 Segment* tmp = current;
147 current = current->next();
148 delete tmp;
149 } else {
150 prev = current;
151 current = current->next();
152 }
153 }
154 size_.fetch_sub(num_deleted, std::memory_order_relaxed);
155 }
156
157 template <typename EntryType, uint16_t SegmentSize>
158 template <typename Callback>
Iterate(Callback callback)159 void Worklist<EntryType, SegmentSize>::Iterate(Callback callback) {
160 v8::base::MutexGuard guard(&lock_);
161 for (Segment* current = top_; current != nullptr; current = current->next()) {
162 current->Iterate(callback);
163 }
164 }
165
166 template <typename EntryType, uint16_t SegmentSize>
Merge(Worklist<EntryType,SegmentSize> * other)167 void Worklist<EntryType, SegmentSize>::Merge(
168 Worklist<EntryType, SegmentSize>* other) {
169 Segment* top = nullptr;
170 size_t other_size = 0;
171 {
172 v8::base::MutexGuard guard(&other->lock_);
173 if (!other->top_) return;
174 top = other->top_;
175 other_size = other->size_.load(std::memory_order_relaxed);
176 other->size_.store(0, std::memory_order_relaxed);
177 other->set_top(nullptr);
178 }
179
180 // It's safe to iterate through these segments because the top was
181 // extracted from |other|.
182 Segment* end = top;
183 while (end->next()) end = end->next();
184
185 {
186 v8::base::MutexGuard guard(&lock_);
187 size_.fetch_add(other_size, std::memory_order_relaxed);
188 end->set_next(top_);
189 set_top(top);
190 }
191 }
192
193 template <typename EntryType, uint16_t SegmentSize>
194 class Worklist<EntryType, SegmentSize>::Segment : public internal::SegmentBase {
195 public:
196 static const uint16_t kSize = SegmentSize;
197
198 void Push(EntryType entry);
199 void Pop(EntryType* entry);
200
201 template <typename Callback>
202 void Update(Callback callback);
203 template <typename Callback>
204 void Iterate(Callback callback) const;
205
next()206 Segment* next() const { return next_; }
set_next(Segment * segment)207 void set_next(Segment* segment) { next_ = segment; }
208
209 private:
Segment()210 Segment() : internal::SegmentBase(kSize) {}
211
212 Segment* next_ = nullptr;
213 EntryType entries_[kSize];
214
215 friend class Worklist<EntryType, SegmentSize>::Local;
216
217 FRIEND_TEST(CppgcWorkListTest, SegmentCreate);
218 FRIEND_TEST(CppgcWorkListTest, SegmentPush);
219 FRIEND_TEST(CppgcWorkListTest, SegmentPushPop);
220 FRIEND_TEST(CppgcWorkListTest, SegmentIsEmpty);
221 FRIEND_TEST(CppgcWorkListTest, SegmentIsFull);
222 FRIEND_TEST(CppgcWorkListTest, SegmentClear);
223 FRIEND_TEST(CppgcWorkListTest, SegmentUpdateFalse);
224 FRIEND_TEST(CppgcWorkListTest, SegmentUpdate);
225 };
226
227 template <typename EntryType, uint16_t SegmentSize>
Push(EntryType entry)228 void Worklist<EntryType, SegmentSize>::Segment::Push(EntryType entry) {
229 DCHECK(!IsFull());
230 entries_[index_++] = entry;
231 }
232
233 template <typename EntryType, uint16_t SegmentSize>
Pop(EntryType * entry)234 void Worklist<EntryType, SegmentSize>::Segment::Pop(EntryType* entry) {
235 DCHECK(!IsEmpty());
236 *entry = entries_[--index_];
237 }
238
239 template <typename EntryType, uint16_t SegmentSize>
240 template <typename Callback>
Update(Callback callback)241 void Worklist<EntryType, SegmentSize>::Segment::Update(Callback callback) {
242 size_t new_index = 0;
243 for (size_t i = 0; i < index_; i++) {
244 if (callback(entries_[i], &entries_[new_index])) {
245 new_index++;
246 }
247 }
248 index_ = new_index;
249 }
250
251 template <typename EntryType, uint16_t SegmentSize>
252 template <typename Callback>
Iterate(Callback callback)253 void Worklist<EntryType, SegmentSize>::Segment::Iterate(
254 Callback callback) const {
255 for (size_t i = 0; i < index_; i++) {
256 callback(entries_[i]);
257 }
258 }
259
260 // A thread-local view of the marking worklist.
261 template <typename EntryType, uint16_t SegmentSize>
262 class Worklist<EntryType, SegmentSize>::Local {
263 public:
264 using ItemType = EntryType;
265
266 Local() = default;
267 explicit Local(Worklist<EntryType, SegmentSize>* worklist);
268 ~Local();
269
270 Local(Local&&) V8_NOEXCEPT;
271 Local& operator=(Local&&) V8_NOEXCEPT;
272
273 // Disable copying since having multiple copies of the same
274 // local marking worklist is unsafe.
275 Local(const Local&) = delete;
276 Local& operator=(const Local& other) = delete;
277
278 void Push(EntryType entry);
279 bool Pop(EntryType* entry);
280
281 bool IsLocalAndGlobalEmpty() const;
282 bool IsLocalEmpty() const;
283 bool IsGlobalEmpty() const;
284
285 void Publish();
286 void Merge(Worklist<EntryType, SegmentSize>::Local* other);
287
288 bool IsEmpty() const;
289 void Clear();
290
PushSegmentSize()291 size_t PushSegmentSize() const { return push_segment_->Size(); }
292
293 private:
294 void PublishPushSegment();
295 void PublishPopSegment();
296 bool StealPopSegment();
297
NewSegment()298 Segment* NewSegment() const {
299 // Bottleneck for filtering in crash dumps.
300 return new Segment();
301 }
DeleteSegment(internal::SegmentBase * segment)302 void DeleteSegment(internal::SegmentBase* segment) const {
303 if (segment == internal::SegmentBase::GetSentinelSegmentAddress()) return;
304 delete static_cast<Segment*>(segment);
305 }
306
push_segment()307 inline Segment* push_segment() {
308 DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(),
309 push_segment_);
310 return static_cast<Segment*>(push_segment_);
311 }
push_segment()312 inline const Segment* push_segment() const {
313 DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(),
314 push_segment_);
315 return static_cast<const Segment*>(push_segment_);
316 }
317
pop_segment()318 inline Segment* pop_segment() {
319 DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(), pop_segment_);
320 return static_cast<Segment*>(pop_segment_);
321 }
pop_segment()322 inline const Segment* pop_segment() const {
323 DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(), pop_segment_);
324 return static_cast<const Segment*>(pop_segment_);
325 }
326
327 Worklist<EntryType, SegmentSize>* worklist_ = nullptr;
328 internal::SegmentBase* push_segment_ = nullptr;
329 internal::SegmentBase* pop_segment_ = nullptr;
330 };
331
332 template <typename EntryType, uint16_t SegmentSize>
Local(Worklist<EntryType,SegmentSize> * worklist)333 Worklist<EntryType, SegmentSize>::Local::Local(
334 Worklist<EntryType, SegmentSize>* worklist)
335 : worklist_(worklist),
336 push_segment_(internal::SegmentBase::GetSentinelSegmentAddress()),
337 pop_segment_(internal::SegmentBase::GetSentinelSegmentAddress()) {}
338
339 template <typename EntryType, uint16_t SegmentSize>
~Local()340 Worklist<EntryType, SegmentSize>::Local::~Local() {
341 CHECK_IMPLIES(push_segment_, push_segment_->IsEmpty());
342 CHECK_IMPLIES(pop_segment_, pop_segment_->IsEmpty());
343 DeleteSegment(push_segment_);
344 DeleteSegment(pop_segment_);
345 }
346
347 template <typename EntryType, uint16_t SegmentSize>
Local(Worklist<EntryType,SegmentSize>::Local && other)348 Worklist<EntryType, SegmentSize>::Local::Local(
349 Worklist<EntryType, SegmentSize>::Local&& other) V8_NOEXCEPT {
350 worklist_ = other.worklist_;
351 push_segment_ = other.push_segment_;
352 pop_segment_ = other.pop_segment_;
353 other.worklist_ = nullptr;
354 other.push_segment_ = nullptr;
355 other.pop_segment_ = nullptr;
356 }
357
358 template <typename EntryType, uint16_t SegmentSize>
359 typename Worklist<EntryType, SegmentSize>::Local&
360 Worklist<EntryType, SegmentSize>::Local::operator=(
361 Worklist<EntryType, SegmentSize>::Local&& other) V8_NOEXCEPT {
362 if (this != &other) {
363 DCHECK_NULL(worklist_);
364 DCHECK_NULL(push_segment_);
365 DCHECK_NULL(pop_segment_);
366 worklist_ = other.worklist_;
367 push_segment_ = other.push_segment_;
368 pop_segment_ = other.pop_segment_;
369 other.worklist_ = nullptr;
370 other.push_segment_ = nullptr;
371 other.pop_segment_ = nullptr;
372 }
373 return *this;
374 }
375
376 template <typename EntryType, uint16_t SegmentSize>
Push(EntryType entry)377 void Worklist<EntryType, SegmentSize>::Local::Push(EntryType entry) {
378 if (V8_UNLIKELY(push_segment_->IsFull())) {
379 PublishPushSegment();
380 }
381 push_segment()->Push(entry);
382 }
383
384 template <typename EntryType, uint16_t SegmentSize>
Pop(EntryType * entry)385 bool Worklist<EntryType, SegmentSize>::Local::Pop(EntryType* entry) {
386 if (pop_segment_->IsEmpty()) {
387 if (!push_segment_->IsEmpty()) {
388 std::swap(push_segment_, pop_segment_);
389 } else if (!StealPopSegment()) {
390 return false;
391 }
392 }
393 pop_segment()->Pop(entry);
394 return true;
395 }
396
397 template <typename EntryType, uint16_t SegmentSize>
IsLocalAndGlobalEmpty()398 bool Worklist<EntryType, SegmentSize>::Local::IsLocalAndGlobalEmpty() const {
399 return IsLocalEmpty() && IsGlobalEmpty();
400 }
401
402 template <typename EntryType, uint16_t SegmentSize>
IsLocalEmpty()403 bool Worklist<EntryType, SegmentSize>::Local::IsLocalEmpty() const {
404 return push_segment_->IsEmpty() && pop_segment_->IsEmpty();
405 }
406
407 template <typename EntryType, uint16_t SegmentSize>
IsGlobalEmpty()408 bool Worklist<EntryType, SegmentSize>::Local::IsGlobalEmpty() const {
409 return worklist_->IsEmpty();
410 }
411
412 template <typename EntryType, uint16_t SegmentSize>
Publish()413 void Worklist<EntryType, SegmentSize>::Local::Publish() {
414 if (!push_segment_->IsEmpty()) PublishPushSegment();
415 if (!pop_segment_->IsEmpty()) PublishPopSegment();
416 }
417
418 template <typename EntryType, uint16_t SegmentSize>
Merge(Worklist<EntryType,SegmentSize>::Local * other)419 void Worklist<EntryType, SegmentSize>::Local::Merge(
420 Worklist<EntryType, SegmentSize>::Local* other) {
421 other->Publish();
422 worklist_->Merge(other->worklist_);
423 }
424
425 template <typename EntryType, uint16_t SegmentSize>
PublishPushSegment()426 void Worklist<EntryType, SegmentSize>::Local::PublishPushSegment() {
427 if (push_segment_ != internal::SegmentBase::GetSentinelSegmentAddress())
428 worklist_->Push(push_segment());
429 push_segment_ = NewSegment();
430 }
431
432 template <typename EntryType, uint16_t SegmentSize>
PublishPopSegment()433 void Worklist<EntryType, SegmentSize>::Local::PublishPopSegment() {
434 if (pop_segment_ != internal::SegmentBase::GetSentinelSegmentAddress())
435 worklist_->Push(pop_segment());
436 pop_segment_ = NewSegment();
437 }
438
439 template <typename EntryType, uint16_t SegmentSize>
StealPopSegment()440 bool Worklist<EntryType, SegmentSize>::Local::StealPopSegment() {
441 if (worklist_->IsEmpty()) return false;
442 Segment* new_segment = nullptr;
443 if (worklist_->Pop(&new_segment)) {
444 DeleteSegment(pop_segment_);
445 pop_segment_ = new_segment;
446 return true;
447 }
448 return false;
449 }
450
451 template <typename EntryType, uint16_t SegmentSize>
IsEmpty()452 bool Worklist<EntryType, SegmentSize>::Local::IsEmpty() const {
453 return push_segment_->IsEmpty() && pop_segment_->IsEmpty();
454 }
455
456 template <typename EntryType, uint16_t SegmentSize>
Clear()457 void Worklist<EntryType, SegmentSize>::Local::Clear() {
458 push_segment_->Clear();
459 pop_segment_->Clear();
460 }
461
462 } // namespace base
463 } // namespace heap
464
465 #endif // V8_HEAP_BASE_WORKLIST_H_
466