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 1080181 : : worklist_(worklist), task_id_(task_id) {}
34 :
35 : // Pushes an entry onto the worklist.
36 368275690 : bool Push(EntryType entry) { return worklist_->Push(task_id_, entry); }
37 :
38 : // Pops an entry from the worklist.
39 54176251 : 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 915927 : Worklist() : Worklist(kMaxNumTasks) {}
63 :
64 1972839 : explicit Worklist(int num_tasks) : num_tasks_(num_tasks) {
65 : DCHECK_LE(num_tasks, kMaxNumTasks);
66 8427585 : for (int i = 0; i < num_tasks_; i++) {
67 7441189 : private_push_segment(i) = NewSegment();
68 7441173 : private_pop_segment(i) = NewSegment();
69 : }
70 986428 : }
71 :
72 986203 : ~Worklist() {
73 986203 : CHECK(IsEmpty());
74 7439385 : 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 7439382 : delete private_push_segment(i);
78 7439384 : delete private_pop_segment(i);
79 : }
80 986203 : }
81 :
82 : // Swaps content with the given worklist. Local buffers need to
83 : // be empty, not thread safe.
84 149056 : void Swap(Worklist<EntryType, SEGMENT_SIZE>& other) {
85 149056 : CHECK(AreLocalsEmpty());
86 149056 : CHECK(other.AreLocalsEmpty());
87 :
88 149056 : global_pool_.Swap(other.global_pool_);
89 149056 : }
90 :
91 829123181 : bool Push(int task_id, EntryType entry) {
92 : DCHECK_LT(task_id, num_tasks_);
93 : DCHECK_NOT_NULL(private_push_segment(task_id));
94 1658246362 : if (!private_push_segment(task_id)->Push(entry)) {
95 : PublishPushSegmentToGlobal(task_id);
96 6961868 : bool success = private_push_segment(task_id)->Push(entry);
97 : USE(success);
98 : DCHECK(success);
99 : }
100 829123257 : return true;
101 : }
102 :
103 823729228 : bool Pop(int task_id, EntryType* entry) {
104 : DCHECK_LT(task_id, num_tasks_);
105 : DCHECK_NOT_NULL(private_pop_segment(task_id));
106 1647458456 : if (!private_pop_segment(task_id)->Pop(entry)) {
107 103843961 : if (!private_push_segment(task_id)->IsEmpty()) {
108 85171810 : Segment* tmp = private_pop_segment(task_id);
109 85171810 : private_pop_segment(task_id) = private_push_segment(task_id);
110 85171810 : private_push_segment(task_id) = tmp;
111 18674669 : } else if (!StealPopSegmentFromGlobal(task_id)) {
112 : return false;
113 : }
114 92374709 : 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 54184044 : return private_push_segment(task_id)->Size();
123 : }
124 :
125 : bool IsLocalEmpty(int task_id) {
126 79568929 : return private_pop_segment(task_id)->IsEmpty() &&
127 79568929 : private_push_segment(task_id)->IsEmpty();
128 : }
129 :
130 : bool IsGlobalPoolEmpty() { return global_pool_.IsEmpty(); }
131 :
132 4065460 : bool IsEmpty() {
133 4065460 : if (!AreLocalsEmpty()) return false;
134 4065440 : return global_pool_.IsEmpty();
135 : }
136 :
137 : bool AreLocalsEmpty() {
138 34458202 : for (int i = 0; i < num_tasks_; i++) {
139 34458224 : 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 761781 : void Clear() {
153 6856021 : for (int i = 0; i < num_tasks_; i++) {
154 6094240 : private_pop_segment(i)->Clear();
155 6094240 : private_push_segment(i)->Clear();
156 : }
157 761781 : global_pool_.Clear();
158 761784 : }
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 7892 : void Update(Callback callback) {
170 65504 : for (int i = 0; i < num_tasks_; i++) {
171 63136 : private_pop_segment(i)->Update(callback);
172 63136 : private_push_segment(i)->Update(callback);
173 : }
174 7892 : global_pool_.Update(callback);
175 7892 : }
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 7307139 : void FlushToGlobal(int task_id) {
197 : PublishPushSegmentToGlobal(task_id);
198 : PublishPopSegmentToGlobal(task_id);
199 7307078 : }
200 :
201 1062068 : void MergeGlobalPool(Worklist* other) {
202 1062068 : auto pair = other->global_pool_.Extract();
203 1062068 : global_pool_.MergeList(pair.first, pair.second);
204 1062068 : }
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 1435985734 : Segment() : index_(0) {}
223 :
224 836085049 : bool Push(EntryType entry) {
225 836085242 : if (IsFull()) return false;
226 829166874 : entries_[index_++] = entry;
227 : return true;
228 : }
229 :
230 916103937 : bool Pop(EntryType* entry) {
231 916103938 : if (IsEmpty()) return false;
232 813427509 : *entry = entries_[--index_];
233 : return true;
234 : }
235 :
236 : size_t Size() const { return index_; }
237 21561151 : bool IsEmpty() const { return index_ == 0; }
238 2 : bool IsFull() const { return index_ == kCapacity; }
239 12188480 : void Clear() { index_ = 0; }
240 :
241 : template <typename Callback>
242 148512 : void Update(Callback callback) {
243 : size_t new_index = 0;
244 1448761 : for (size_t i = 0; i < index_; i++) {
245 1393240 : if (callback(entries_[i], &entries_[new_index])) {
246 1301326 : new_index++;
247 : }
248 : }
249 148547 : index_ = new_index;
250 148512 : }
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 7204125 : Segment* next() const { return next_; }
260 7280542 : 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 986203 : class GlobalPool {
275 : public:
276 986427 : GlobalPool() : top_(nullptr) {}
277 :
278 : // Swaps contents, not thread safe.
279 149056 : void Swap(GlobalPool& other) {
280 149056 : Segment* temp = top_;
281 149056 : set_top(other.top_);
282 : other.set_top(temp);
283 149056 : }
284 :
285 : V8_INLINE void Push(Segment* segment) {
286 7258111 : base::MutexGuard guard(&lock_);
287 7258385 : segment->set_next(top_);
288 7258385 : set_top(segment);
289 : }
290 :
291 : V8_INLINE bool Pop(Segment** segment) {
292 7201413 : base::MutexGuard guard(&lock_);
293 7204730 : if (top_ != nullptr) {
294 : *segment = top_;
295 7204125 : set_top(top_->next());
296 : return true;
297 : }
298 7204730 : return false;
299 : }
300 :
301 : V8_INLINE bool IsEmpty() {
302 30238890 : return base::AsAtomicPointer::Relaxed_Load(&top_) == nullptr;
303 : }
304 :
305 761781 : void Clear() {
306 761781 : base::MutexGuard guard(&lock_);
307 815092 : Segment* current = top_;
308 1576877 : while (current != nullptr) {
309 : Segment* tmp = current;
310 : current = current->next();
311 53307 : delete tmp;
312 : }
313 : set_top(nullptr);
314 761784 : }
315 :
316 : // See Worklist::Update.
317 : template <typename Callback>
318 7892 : void Update(Callback callback) {
319 7892 : base::MutexGuard guard(&lock_);
320 : Segment* prev = nullptr;
321 53402 : Segment* current = top_;
322 32535 : while (current != nullptr) {
323 22272 : current->Update(callback);
324 22274 : if (current->IsEmpty()) {
325 962 : if (prev == nullptr) {
326 553 : top_ = current->next();
327 : } else {
328 : prev->set_next(current->next());
329 : }
330 : Segment* tmp = current;
331 : current = current->next();
332 963 : delete tmp;
333 : } else {
334 : prev = current;
335 : current = current->next();
336 : }
337 : }
338 7892 : }
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 1062068 : std::pair<Segment*, Segment*> Extract() {
351 : Segment* top = nullptr;
352 : {
353 1062068 : base::MutexGuard guard(&lock_);
354 1062068 : if (top_ == nullptr) return std::make_pair(nullptr, nullptr);
355 : top = top_;
356 : set_top(nullptr);
357 : }
358 : Segment* end = top;
359 21754 : while (end->next() != nullptr) end = end->next();
360 : return std::make_pair(top, end);
361 : }
362 :
363 1062068 : void MergeList(Segment* start, Segment* end) {
364 2124136 : if (start == nullptr) return;
365 : {
366 21754 : base::MutexGuard guard(&lock_);
367 21754 : end->set_next(top_);
368 : set_top(start);
369 : }
370 : }
371 :
372 : private:
373 14462090 : void set_top(Segment* segment) {
374 15565495 : base::AsAtomicPointer::Relaxed_Store(&top_, segment);
375 14462090 : }
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 14268931 : if (!private_push_segment(task_id)->IsEmpty()) {
391 7257820 : global_pool_.Push(private_push_segment(task_id));
392 7257895 : private_push_segment(task_id) = NewSegment();
393 : }
394 : }
395 :
396 : V8_INLINE void PublishPopSegmentToGlobal(int task_id) {
397 7307857 : if (!private_pop_segment(task_id)->IsEmpty()) {
398 291 : global_pool_.Push(private_pop_segment(task_id));
399 291 : private_pop_segment(task_id) = NewSegment();
400 : }
401 : }
402 :
403 : V8_INLINE bool StealPopSegmentFromGlobal(int task_id) {
404 18671449 : if (global_pool_.IsEmpty()) return false;
405 : Segment* new_segment = nullptr;
406 14405948 : if (global_pool_.Pop(&new_segment)) {
407 7203940 : delete private_pop_segment(task_id);
408 7204038 : 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 22140697 : 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_
|
