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