Line data Source code
1 : // Copyright 2017 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_WORKLIST_H_
6 : #define V8_HEAP_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/macros.h"
14 : #include "src/base/platform/mutex.h"
15 : #include "testing/gtest/include/gtest/gtest_prod.h" // nogncheck
16 :
17 : namespace v8 {
18 : namespace internal {
19 :
20 : // A concurrent worklist based on segments. Each tasks gets private
21 : // push and pop segments. Empty pop segments are swapped with their
22 : // corresponding push segments. Full push segments are published to a global
23 : // pool of segments and replaced with empty segments.
24 : //
25 : // Work stealing is best effort, i.e., there is no way to inform other tasks
26 : // of the need of items.
27 : template <typename EntryType, int SEGMENT_SIZE>
28 : class Worklist {
29 : public:
30 : class View {
31 : public:
32 : View(Worklist<EntryType, SEGMENT_SIZE>* worklist, int task_id)
33 1022141 : : worklist_(worklist), task_id_(task_id) {}
34 :
35 : // Pushes an entry onto the worklist.
36 334251256 : bool Push(EntryType entry) { return worklist_->Push(task_id_, entry); }
37 :
38 : // Pops an entry from the worklist.
39 54745352 : bool Pop(EntryType* entry) { return worklist_->Pop(task_id_, entry); }
40 :
41 : // Returns true if the local portion of the worklist is empty.
42 : bool IsLocalEmpty() { return worklist_->IsLocalEmpty(task_id_); }
43 :
44 : // Returns true if the worklist is empty. Can only be used from the main
45 : // thread without concurrent access.
46 : bool IsEmpty() { return worklist_->IsEmpty(); }
47 :
48 : bool IsGlobalPoolEmpty() { return worklist_->IsGlobalPoolEmpty(); }
49 :
50 : size_t LocalPushSegmentSize() {
51 : return worklist_->LocalPushSegmentSize(task_id_);
52 : }
53 :
54 47523 : void FlushToGlobal() { worklist_->FlushToGlobal(task_id_); }
55 :
56 : private:
57 : Worklist<EntryType, SEGMENT_SIZE>* worklist_;
58 : int task_id_;
59 : };
60 :
61 : static const int kMaxNumTasks = 8;
62 : static const size_t kSegmentCapacity = SEGMENT_SIZE;
63 :
64 936823 : Worklist() : Worklist(kMaxNumTasks) {}
65 :
66 2082476 : explicit Worklist(int num_tasks) : num_tasks_(num_tasks) {
67 : DCHECK_LE(num_tasks, kMaxNumTasks);
68 16411021 : for (int i = 0; i < num_tasks_; i++) {
69 7684879 : private_push_segment(i) = NewSegment();
70 7684895 : private_pop_segment(i) = NewSegment();
71 : }
72 1041245 : }
73 :
74 1041012 : ~Worklist() {
75 1041012 : CHECK(IsEmpty());
76 16407219 : for (int i = 0; i < num_tasks_; i++) {
77 : DCHECK_NOT_NULL(private_push_segment(i));
78 : DCHECK_NOT_NULL(private_pop_segment(i));
79 7683099 : delete private_push_segment(i);
80 7683107 : delete private_pop_segment(i);
81 : }
82 1041015 : }
83 :
84 : // Swaps content with the given worklist. Local buffers need to
85 : // be empty, not thread safe.
86 137731 : void Swap(Worklist<EntryType, SEGMENT_SIZE>& other) {
87 137731 : CHECK(AreLocalsEmpty());
88 137731 : CHECK(other.AreLocalsEmpty());
89 :
90 137731 : global_pool_.Swap(other.global_pool_);
91 137731 : }
92 :
93 755821764 : bool Push(int task_id, EntryType entry) {
94 : DCHECK_LT(task_id, num_tasks_);
95 : DCHECK_NOT_NULL(private_push_segment(task_id));
96 1511643528 : if (!private_push_segment(task_id)->Push(entry)) {
97 : PublishPushSegmentToGlobal(task_id);
98 6263284 : bool success = private_push_segment(task_id)->Push(entry);
99 : USE(success);
100 : DCHECK(success);
101 : }
102 755821338 : return true;
103 : }
104 :
105 729447470 : bool Pop(int task_id, EntryType* entry) {
106 : DCHECK_LT(task_id, num_tasks_);
107 : DCHECK_NOT_NULL(private_pop_segment(task_id));
108 1458894940 : if (!private_pop_segment(task_id)->Pop(entry)) {
109 95876457 : if (!private_push_segment(task_id)->IsEmpty()) {
110 80261658 : Segment* tmp = private_pop_segment(task_id);
111 80261658 : private_pop_segment(task_id) = private_push_segment(task_id);
112 80261658 : private_push_segment(task_id) = tmp;
113 15620159 : } else if (!StealPopSegmentFromGlobal(task_id)) {
114 : return false;
115 : }
116 86787950 : bool success = private_pop_segment(task_id)->Pop(entry);
117 : USE(success);
118 : DCHECK(success);
119 : }
120 : return true;
121 : }
122 :
123 : size_t LocalPushSegmentSize(int task_id) {
124 54693825 : return private_push_segment(task_id)->Size();
125 : }
126 :
127 : bool IsLocalEmpty(int task_id) {
128 88933468 : return private_pop_segment(task_id)->IsEmpty() &&
129 88933468 : private_push_segment(task_id)->IsEmpty();
130 : }
131 :
132 : bool IsGlobalPoolEmpty() { return global_pool_.IsEmpty(); }
133 :
134 4766098 : bool IsEmpty() {
135 4766098 : if (!AreLocalsEmpty()) return false;
136 4766078 : return global_pool_.IsEmpty();
137 : }
138 :
139 : bool AreLocalsEmpty() {
140 84415952 : for (int i = 0; i < num_tasks_; i++) {
141 39687197 : if (!IsLocalEmpty(i)) return false;
142 : }
143 : return true;
144 : }
145 :
146 : size_t LocalSize(int task_id) {
147 : return private_pop_segment(task_id)->Size() +
148 : private_push_segment(task_id)->Size();
149 : }
150 :
151 : // Clears all segments. Frees the global segment pool.
152 : //
153 : // Assumes that no other tasks are running.
154 : void Clear() {
155 13222837 : for (int i = 0; i < num_tasks_; i++) {
156 6213019 : private_pop_segment(i)->Clear();
157 6213019 : private_push_segment(i)->Clear();
158 : }
159 796799 : global_pool_.Clear();
160 : }
161 :
162 : // Calls the specified callback on each element of the deques and replaces
163 : // the element with the result of the callback.
164 : // The signature of the callback is
165 : // bool Callback(EntryType old, EntryType* new).
166 : // If the callback returns |false| then the element is removed from the
167 : // worklist. Otherwise the |new| entry is updated.
168 : //
169 : // Assumes that no other tasks are running.
170 : template <typename Callback>
171 11072 : void Update(Callback callback) {
172 188224 : for (int i = 0; i < num_tasks_; i++) {
173 88576 : private_pop_segment(i)->Update(callback);
174 88576 : private_push_segment(i)->Update(callback);
175 : }
176 11072 : global_pool_.Update(callback);
177 11072 : }
178 :
179 : // Calls the specified callback on each element of the deques.
180 : // The signature of the callback is:
181 : // void Callback(EntryType entry).
182 : //
183 : // Assumes that no other tasks are running.
184 : template <typename Callback>
185 26098 : void Iterate(Callback callback) {
186 121144 : for (int i = 0; i < num_tasks_; i++) {
187 47523 : private_pop_segment(i)->Iterate(callback);
188 47523 : private_push_segment(i)->Iterate(callback);
189 : }
190 26098 : global_pool_.Iterate(callback);
191 26098 : }
192 :
193 : template <typename Callback>
194 : void IterateGlobalPool(Callback callback) {
195 0 : global_pool_.Iterate(callback);
196 : }
197 :
198 6844813 : void FlushToGlobal(int task_id) {
199 : PublishPushSegmentToGlobal(task_id);
200 : PublishPopSegmentToGlobal(task_id);
201 6844799 : }
202 :
203 1086599 : void MergeGlobalPool(Worklist* other) {
204 1086599 : auto pair = other->global_pool_.Extract();
205 1086600 : global_pool_.MergeList(pair.first, pair.second);
206 1086600 : }
207 :
208 : private:
209 : FRIEND_TEST(WorkListTest, SegmentCreate);
210 : FRIEND_TEST(WorkListTest, SegmentPush);
211 : FRIEND_TEST(WorkListTest, SegmentPushPop);
212 : FRIEND_TEST(WorkListTest, SegmentIsEmpty);
213 : FRIEND_TEST(WorkListTest, SegmentIsFull);
214 : FRIEND_TEST(WorkListTest, SegmentClear);
215 : FRIEND_TEST(WorkListTest, SegmentFullPushFails);
216 : FRIEND_TEST(WorkListTest, SegmentEmptyPopFails);
217 : FRIEND_TEST(WorkListTest, SegmentUpdateFalse);
218 : FRIEND_TEST(WorkListTest, SegmentUpdate);
219 :
220 : class Segment {
221 : public:
222 : static const size_t kCapacity = kSegmentCapacity;
223 :
224 108136582 : Segment() : index_(0) {}
225 :
226 : bool Push(EntryType entry) {
227 762085241 : if (IsFull()) return false;
228 756189417 : entries_[index_++] = entry;
229 : return true;
230 : }
231 :
232 : bool Pop(EntryType* entry) {
233 816235421 : if (IsEmpty()) return false;
234 723157692 : *entry = entries_[--index_];
235 : return true;
236 : }
237 :
238 : size_t Size() const { return index_; }
239 : bool IsEmpty() const { return index_ == 0; }
240 2 : bool IsFull() const { return index_ == kCapacity; }
241 12426038 : void Clear() { index_ = 0; }
242 :
243 : template <typename Callback>
244 194710 : void Update(Callback callback) {
245 : size_t new_index = 0;
246 2303735 : for (size_t i = 0; i < index_; i++) {
247 1295436 : if (callback(entries_[i], &entries_[new_index])) {
248 1011403 : new_index++;
249 : }
250 : }
251 194745 : index_ = new_index;
252 194710 : }
253 :
254 : template <typename Callback>
255 : void Iterate(Callback callback) const {
256 164702 : for (size_t i = 0; i < index_; i++) {
257 34641 : callback(entries_[i]);
258 : }
259 : }
260 :
261 6535335 : Segment* next() const { return next_; }
262 6605665 : void set_next(Segment* segment) { next_ = segment; }
263 :
264 : private:
265 : Segment* next_;
266 : size_t index_;
267 : EntryType entries_[kCapacity];
268 : };
269 :
270 : struct PrivateSegmentHolder {
271 : Segment* private_push_segment;
272 : Segment* private_pop_segment;
273 : char cache_line_padding[64];
274 : };
275 :
276 1041020 : class GlobalPool {
277 : public:
278 1041245 : GlobalPool() : top_(nullptr) {}
279 :
280 : // Swaps contents, not thread safe.
281 137731 : void Swap(GlobalPool& other) {
282 137731 : Segment* temp = top_;
283 137731 : set_top(other.top_);
284 : other.set_top(temp);
285 137731 : }
286 :
287 : V8_INLINE void Push(Segment* segment) {
288 6582966 : base::MutexGuard guard(&lock_);
289 6583395 : segment->set_next(top_);
290 6583371 : set_top(segment);
291 : }
292 :
293 : V8_INLINE bool Pop(Segment** segment) {
294 6529943 : base::MutexGuard guard(&lock_);
295 6536628 : if (top_ != nullptr) {
296 : *segment = top_;
297 6535349 : set_top(top_->next());
298 : return true;
299 : }
300 : return false;
301 : }
302 :
303 : V8_INLINE bool IsEmpty() {
304 26294518 : return base::AsAtomicPointer::Relaxed_Load(&top_) == nullptr;
305 : }
306 :
307 796798 : void Clear() {
308 796798 : base::MutexGuard guard(&lock_);
309 796806 : Segment* current = top_;
310 892290 : while (current != nullptr) {
311 : Segment* tmp = current;
312 : current = current->next();
313 47742 : delete tmp;
314 : }
315 : set_top(nullptr);
316 796806 : }
317 :
318 : // See Worklist::Update.
319 : template <typename Callback>
320 11072 : void Update(Callback callback) {
321 11072 : base::MutexGuard guard(&lock_);
322 : Segment* prev = nullptr;
323 11072 : Segment* current = top_;
324 28665 : while (current != nullptr) {
325 17590 : current->Update(callback);
326 17592 : if (current->IsEmpty()) {
327 403 : if (prev == nullptr) {
328 196 : top_ = current->next();
329 : } else {
330 : prev->set_next(current->next());
331 : }
332 : Segment* tmp = current;
333 : current = current->next();
334 403 : delete tmp;
335 : } else {
336 : prev = current;
337 : current = current->next();
338 : }
339 : }
340 11072 : }
341 :
342 : // See Worklist::Iterate.
343 : template <typename Callback>
344 26098 : void Iterate(Callback callback) {
345 26098 : base::MutexGuard guard(&lock_);
346 26098 : for (Segment* current = top_; current != nullptr;
347 : current = current->next()) {
348 : current->Iterate(callback);
349 : }
350 26098 : }
351 :
352 1086599 : std::pair<Segment*, Segment*> Extract() {
353 : Segment* top = nullptr;
354 : {
355 1086599 : base::MutexGuard guard(&lock_);
356 1086600 : if (top_ == nullptr) return std::make_pair(nullptr, nullptr);
357 : top = top_;
358 : set_top(nullptr);
359 : }
360 : Segment* end = top;
361 79582 : while (end->next() != nullptr) end = end->next();
362 : return std::make_pair(top, end);
363 : }
364 :
365 1086599 : void MergeList(Segment* start, Segment* end) {
366 1086599 : if (start == nullptr) return;
367 : {
368 22110 : base::MutexGuard guard(&lock_);
369 22110 : end->set_next(top_);
370 : set_top(start);
371 : }
372 : }
373 :
374 : private:
375 13118322 : void set_top(Segment* segment) {
376 14234810 : base::AsAtomicPointer::Relaxed_Store(&top_, segment);
377 13118322 : }
378 :
379 : base::Mutex lock_;
380 : Segment* top_;
381 : };
382 :
383 : V8_INLINE Segment*& private_push_segment(int task_id) {
384 : return private_segments_[task_id].private_push_segment;
385 : }
386 :
387 : V8_INLINE Segment*& private_pop_segment(int task_id) {
388 : return private_segments_[task_id].private_pop_segment;
389 : }
390 :
391 : V8_INLINE void PublishPushSegmentToGlobal(int task_id) {
392 13108523 : if (!private_push_segment(task_id)->IsEmpty()) {
393 6578054 : global_pool_.Push(private_push_segment(task_id));
394 6577613 : private_push_segment(task_id) = NewSegment();
395 : }
396 : }
397 :
398 : V8_INLINE void PublishPopSegmentToGlobal(int task_id) {
399 6844798 : if (!private_pop_segment(task_id)->IsEmpty()) {
400 4902 : global_pool_.Push(private_pop_segment(task_id));
401 4903 : private_pop_segment(task_id) = NewSegment();
402 : }
403 : }
404 :
405 : V8_INLINE bool StealPopSegmentFromGlobal(int task_id) {
406 15613719 : if (global_pool_.IsEmpty()) return false;
407 : Segment* new_segment = nullptr;
408 13066354 : if (global_pool_.Pop(&new_segment)) {
409 6535150 : delete private_pop_segment(task_id);
410 6535108 : private_pop_segment(task_id) = new_segment;
411 : return true;
412 : }
413 : return false;
414 : }
415 :
416 : V8_INLINE Segment* NewSegment() {
417 : // Bottleneck for filtering in crash dumps.
418 21953137 : return new Segment();
419 : }
420 :
421 : PrivateSegmentHolder private_segments_[kMaxNumTasks];
422 : GlobalPool global_pool_;
423 : int num_tasks_;
424 : };
425 :
426 : } // namespace internal
427 : } // namespace v8
428 :
429 : #endif // V8_HEAP_WORKLIST_H_
|
