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 1106106 : : worklist_(worklist), task_id_(task_id) {}
34 :
35 : // Pushes an entry onto the worklist.
36 402596914 : bool Push(EntryType entry) { return worklist_->Push(task_id_, entry); }
37 :
38 : // Pops an entry from the worklist.
39 63762969 : 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 : private:
55 : Worklist<EntryType, SEGMENT_SIZE>* worklist_;
56 : int task_id_;
57 : };
58 :
59 : static const int kMaxNumTasks = 8;
60 : static const size_t kSegmentCapacity = SEGMENT_SIZE;
61 :
62 880539 : Worklist() : Worklist(kMaxNumTasks) {}
63 :
64 1902672 : explicit Worklist(int num_tasks) : num_tasks_(num_tasks) {
65 : DCHECK_LE(num_tasks, kMaxNumTasks);
66 8108734 : for (int i = 0; i < num_tasks_; i++) {
67 7157428 : private_push_segment(i) = NewSegment();
68 7157413 : private_pop_segment(i) = NewSegment();
69 : }
70 951352 : }
71 :
72 951136 : ~Worklist() {
73 951136 : CHECK(IsEmpty());
74 7155722 : for (int i = 0; i < num_tasks_; i++) {
75 : DCHECK_NOT_NULL(private_push_segment(i));
76 : DCHECK_NOT_NULL(private_pop_segment(i));
77 7155716 : delete private_push_segment(i);
78 7155722 : delete private_pop_segment(i);
79 : }
80 951140 : }
81 :
82 : // Swaps content with the given worklist. Local buffers need to
83 : // be empty, not thread safe.
84 167031 : void Swap(Worklist<EntryType, SEGMENT_SIZE>& other) {
85 167031 : CHECK(AreLocalsEmpty());
86 167031 : CHECK(other.AreLocalsEmpty());
87 :
88 167031 : global_pool_.Swap(other.global_pool_);
89 167031 : }
90 :
91 881612838 : bool Push(int task_id, EntryType entry) {
92 : DCHECK_LT(task_id, num_tasks_);
93 : DCHECK_NOT_NULL(private_push_segment(task_id));
94 1763225676 : if (!private_push_segment(task_id)->Push(entry)) {
95 : PublishPushSegmentToGlobal(task_id);
96 7293423 : bool success = private_push_segment(task_id)->Push(entry);
97 : USE(success);
98 : DCHECK(success);
99 : }
100 881612935 : return true;
101 : }
102 :
103 882541408 : bool Pop(int task_id, EntryType* entry) {
104 : DCHECK_LT(task_id, num_tasks_);
105 : DCHECK_NOT_NULL(private_pop_segment(task_id));
106 1765082816 : if (!private_pop_segment(task_id)->Pop(entry)) {
107 100197379 : if (!private_push_segment(task_id)->IsEmpty()) {
108 80514629 : Segment* tmp = private_pop_segment(task_id);
109 80514629 : private_pop_segment(task_id) = private_push_segment(task_id);
110 80514629 : private_push_segment(task_id) = tmp;
111 19685481 : } else if (!StealPopSegmentFromGlobal(task_id)) {
112 : return false;
113 : }
114 88079961 : bool success = private_pop_segment(task_id)->Pop(entry);
115 : USE(success);
116 : DCHECK(success);
117 : }
118 : return true;
119 : }
120 :
121 : size_t LocalPushSegmentSize(int task_id) {
122 63770452 : return private_push_segment(task_id)->Size();
123 : }
124 :
125 : bool IsLocalEmpty(int task_id) {
126 91880994 : return private_pop_segment(task_id)->IsEmpty() &&
127 91880994 : private_push_segment(task_id)->IsEmpty();
128 : }
129 :
130 : bool IsGlobalPoolEmpty() { return global_pool_.IsEmpty(); }
131 :
132 4661650 : bool IsEmpty() {
133 4661650 : if (!AreLocalsEmpty()) return false;
134 4661634 : return global_pool_.IsEmpty();
135 : }
136 :
137 : bool AreLocalsEmpty() {
138 39512129 : for (int i = 0; i < num_tasks_; i++) {
139 39512139 : if (!IsLocalEmpty(i)) return false;
140 : }
141 : return true;
142 : }
143 :
144 : size_t LocalSize(int task_id) {
145 : return private_pop_segment(task_id)->Size() +
146 : private_push_segment(task_id)->Size();
147 : }
148 :
149 : // Clears all segments. Frees the global segment pool.
150 : //
151 : // Assumes that no other tasks are running.
152 713776 : void Clear() {
153 6423936 : for (int i = 0; i < num_tasks_; i++) {
154 5710160 : private_pop_segment(i)->Clear();
155 5710160 : private_push_segment(i)->Clear();
156 : }
157 713776 : global_pool_.Clear();
158 713781 : }
159 :
160 : // Calls the specified callback on each element of the deques and replaces
161 : // the element with the result of the callback.
162 : // The signature of the callback is
163 : // bool Callback(EntryType old, EntryType* new).
164 : // If the callback returns |false| then the element is removed from the
165 : // worklist. Otherwise the |new| entry is updated.
166 : //
167 : // Assumes that no other tasks are running.
168 : template <typename Callback>
169 5726 : void Update(Callback callback) {
170 47717 : for (int i = 0; i < num_tasks_; i++) {
171 45808 : private_pop_segment(i)->Update(callback);
172 45808 : private_push_segment(i)->Update(callback);
173 : }
174 5726 : global_pool_.Update(callback);
175 5726 : }
176 :
177 : // Calls the specified callback on each element of the deques.
178 : // The signature of the callback is:
179 : // void Callback(EntryType entry).
180 : //
181 : // Assumes that no other tasks are running.
182 : template <typename Callback>
183 0 : void Iterate(Callback callback) {
184 0 : for (int i = 0; i < num_tasks_; i++) {
185 0 : private_pop_segment(i)->Iterate(callback);
186 0 : private_push_segment(i)->Iterate(callback);
187 : }
188 0 : global_pool_.Iterate(callback);
189 0 : }
190 :
191 : template <typename Callback>
192 : void IterateGlobalPool(Callback callback) {
193 0 : global_pool_.Iterate(callback);
194 : }
195 :
196 7027495 : void FlushToGlobal(int task_id) {
197 : PublishPushSegmentToGlobal(task_id);
198 : PublishPopSegmentToGlobal(task_id);
199 7027491 : }
200 :
201 1294882 : void MergeGlobalPool(Worklist* other) {
202 1294882 : auto pair = other->global_pool_.Extract();
203 1294883 : global_pool_.MergeList(pair.first, pair.second);
204 1294883 : }
205 :
206 : private:
207 : FRIEND_TEST(WorkListTest, SegmentCreate);
208 : FRIEND_TEST(WorkListTest, SegmentPush);
209 : FRIEND_TEST(WorkListTest, SegmentPushPop);
210 : FRIEND_TEST(WorkListTest, SegmentIsEmpty);
211 : FRIEND_TEST(WorkListTest, SegmentIsFull);
212 : FRIEND_TEST(WorkListTest, SegmentClear);
213 : FRIEND_TEST(WorkListTest, SegmentFullPushFails);
214 : FRIEND_TEST(WorkListTest, SegmentEmptyPopFails);
215 : FRIEND_TEST(WorkListTest, SegmentUpdateFalse);
216 : FRIEND_TEST(WorkListTest, SegmentUpdate);
217 :
218 : class Segment {
219 : public:
220 : static const size_t kCapacity = kSegmentCapacity;
221 :
222 1421831910 : Segment() : index_(0) {}
223 :
224 888906261 : bool Push(EntryType entry) {
225 888906454 : if (IsFull()) return false;
226 881695608 : entries_[index_++] = entry;
227 : return true;
228 : }
229 :
230 970621369 : bool Pop(EntryType* entry) {
231 970621370 : if (IsEmpty()) return false;
232 871637479 : *entry = entries_[--index_];
233 : return true;
234 : }
235 :
236 : size_t Size() const { return index_; }
237 21333295 : bool IsEmpty() const { return index_ == 0; }
238 2 : bool IsFull() const { return index_ == kCapacity; }
239 11420320 : void Clear() { index_ = 0; }
240 :
241 : template <typename Callback>
242 105511 : void Update(Callback callback) {
243 : size_t new_index = 0;
244 923028 : for (size_t i = 0; i < index_; i++) {
245 880488 : if (callback(entries_[i], &entries_[new_index])) {
246 785432 : new_index++;
247 : }
248 : }
249 105546 : index_ = new_index;
250 105511 : }
251 :
252 : template <typename Callback>
253 : void Iterate(Callback callback) const {
254 0 : for (size_t i = 0; i < index_; i++) {
255 0 : callback(entries_[i]);
256 : }
257 : }
258 :
259 7565738 : Segment* next() const { return next_; }
260 7593108 : void set_next(Segment* segment) { next_ = segment; }
261 :
262 : private:
263 : Segment* next_;
264 : size_t index_;
265 : EntryType entries_[kCapacity];
266 : };
267 :
268 : struct PrivateSegmentHolder {
269 : Segment* private_push_segment;
270 : Segment* private_pop_segment;
271 : char cache_line_padding[64];
272 : };
273 :
274 951142 : class GlobalPool {
275 : public:
276 951351 : GlobalPool() : top_(nullptr) {}
277 :
278 : // Swaps contents, not thread safe.
279 167031 : void Swap(GlobalPool& other) {
280 167031 : Segment* temp = top_;
281 167031 : set_top(other.top_);
282 : other.set_top(temp);
283 167031 : }
284 :
285 : V8_INLINE void Push(Segment* segment) {
286 7570396 : base::MutexGuard guard(&lock_);
287 7570857 : segment->set_next(top_);
288 7570830 : set_top(segment);
289 : }
290 :
291 : V8_INLINE bool Pop(Segment** segment) {
292 7562982 : base::MutexGuard guard(&lock_);
293 7566356 : if (top_ != nullptr) {
294 : *segment = top_;
295 7565738 : set_top(top_->next());
296 : return true;
297 : }
298 7566356 : return false;
299 : }
300 :
301 : V8_INLINE bool IsEmpty() {
302 33301920 : return base::AsAtomicPointer::Relaxed_Load(&top_) == nullptr;
303 : }
304 :
305 713776 : void Clear() {
306 713776 : base::MutexGuard guard(&lock_);
307 717759 : Segment* current = top_;
308 1431540 : while (current != nullptr) {
309 : Segment* tmp = current;
310 : current = current->next();
311 3978 : delete tmp;
312 : }
313 : set_top(nullptr);
314 713781 : }
315 :
316 : // See Worklist::Update.
317 : template <typename Callback>
318 5726 : void Update(Callback callback) {
319 5726 : base::MutexGuard guard(&lock_);
320 : Segment* prev = nullptr;
321 34823 : Segment* current = top_;
322 21565 : while (current != nullptr) {
323 13927 : current->Update(callback);
324 13929 : if (current->IsEmpty()) {
325 1239 : if (prev == nullptr) {
326 573 : top_ = current->next();
327 : } else {
328 : prev->set_next(current->next());
329 : }
330 : Segment* tmp = current;
331 : current = current->next();
332 1240 : delete tmp;
333 : } else {
334 : prev = current;
335 : current = current->next();
336 : }
337 : }
338 5726 : }
339 :
340 : // See Worklist::Iterate.
341 : template <typename Callback>
342 0 : void Iterate(Callback callback) {
343 0 : base::MutexGuard guard(&lock_);
344 0 : for (Segment* current = top_; current != nullptr;
345 : current = current->next()) {
346 : current->Iterate(callback);
347 : }
348 0 : }
349 :
350 1294882 : std::pair<Segment*, Segment*> Extract() {
351 : Segment* top = nullptr;
352 : {
353 1294882 : base::MutexGuard guard(&lock_);
354 1294883 : if (top_ == nullptr) return std::make_pair(nullptr, nullptr);
355 : top = top_;
356 : set_top(nullptr);
357 : }
358 : Segment* end = top;
359 21596 : while (end->next() != nullptr) end = end->next();
360 : return std::make_pair(top, end);
361 : }
362 :
363 1294882 : void MergeList(Segment* start, Segment* end) {
364 2589764 : if (start == nullptr) return;
365 : {
366 21596 : base::MutexGuard guard(&lock_);
367 21596 : end->set_next(top_);
368 : set_top(start);
369 : }
370 : }
371 :
372 : private:
373 15136280 : void set_top(Segment* segment) {
374 16227315 : base::AsAtomicPointer::Relaxed_Store(&top_, segment);
375 15136280 : }
376 :
377 : base::Mutex lock_;
378 : Segment* top_;
379 : };
380 :
381 : V8_INLINE Segment*& private_push_segment(int task_id) {
382 : return private_segments_[task_id].private_push_segment;
383 : }
384 :
385 : V8_INLINE Segment*& private_pop_segment(int task_id) {
386 : return private_segments_[task_id].private_pop_segment;
387 : }
388 :
389 : V8_INLINE void PublishPushSegmentToGlobal(int task_id) {
390 14320821 : if (!private_push_segment(task_id)->IsEmpty()) {
391 7570255 : global_pool_.Push(private_push_segment(task_id));
392 7570439 : private_push_segment(task_id) = NewSegment();
393 : }
394 : }
395 :
396 : V8_INLINE void PublishPopSegmentToGlobal(int task_id) {
397 7028163 : if (!private_pop_segment(task_id)->IsEmpty()) {
398 141 : global_pool_.Push(private_pop_segment(task_id));
399 141 : private_pop_segment(task_id) = NewSegment();
400 : }
401 : }
402 :
403 : V8_INLINE bool StealPopSegmentFromGlobal(int task_id) {
404 19682203 : if (global_pool_.IsEmpty()) return false;
405 : Segment* new_segment = nullptr;
406 15129144 : if (global_pool_.Pop(&new_segment)) {
407 7565541 : delete private_pop_segment(task_id);
408 7565639 : private_pop_segment(task_id) = new_segment;
409 : return true;
410 : }
411 : return false;
412 : }
413 :
414 : V8_INLINE Segment* NewSegment() {
415 : // Bottleneck for filtering in crash dumps.
416 21885605 : return new Segment();
417 : }
418 :
419 : PrivateSegmentHolder private_segments_[kMaxNumTasks];
420 : GlobalPool global_pool_;
421 : int num_tasks_;
422 : };
423 :
424 : } // namespace internal
425 : } // namespace v8
426 :
427 : #endif // V8_HEAP_WORKLIST_H_
|
