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_
6 : #define V8_HEAP_WORKLIST_
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 330792 : : worklist_(worklist), task_id_(task_id) {}
34 :
35 : // Pushes an entry onto the worklist.
36 412989409 : bool Push(EntryType entry) { return worklist_->Push(task_id_, entry); }
37 :
38 : // Pops an entry from the worklist.
39 95771574 : 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 IsGlobalEmpty() { return worklist_->IsGlobalEmpty(); }
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 330043 : Worklist() : Worklist(kMaxNumTasks) {}
63 :
64 778730 : explicit Worklist(int num_tasks) : num_tasks_(num_tasks) {
65 3118693 : for (int i = 0; i < num_tasks_; i++) {
66 2729344 : private_push_segment(i) = NewSegment();
67 2729334 : private_pop_segment(i) = NewSegment();
68 : }
69 389370 : }
70 :
71 379567 : ~Worklist() {
72 379567 : CHECK(IsGlobalEmpty());
73 2650916 : for (int i = 0; i < num_tasks_; i++) {
74 : DCHECK_NOT_NULL(private_push_segment(i));
75 : DCHECK_NOT_NULL(private_pop_segment(i));
76 2650916 : delete private_push_segment(i);
77 2650916 : delete private_pop_segment(i);
78 : }
79 379567 : }
80 :
81 811128988 : bool Push(int task_id, EntryType entry) {
82 : DCHECK_LT(task_id, num_tasks_);
83 : DCHECK_NOT_NULL(private_push_segment(task_id));
84 1622257976 : if (!private_push_segment(task_id)->Push(entry)) {
85 : PublishPushSegmentToGlobal(task_id);
86 8314672 : bool success = private_push_segment(task_id)->Push(entry);
87 : USE(success);
88 : DCHECK(success);
89 : }
90 811129270 : return true;
91 : }
92 :
93 982816723 : bool Pop(int task_id, EntryType* entry) {
94 : DCHECK_LT(task_id, num_tasks_);
95 : DCHECK_NOT_NULL(private_pop_segment(task_id));
96 1965633446 : if (!private_pop_segment(task_id)->Pop(entry)) {
97 259244287 : if (!private_push_segment(task_id)->IsEmpty()) {
98 65040004 : Segment* tmp = private_pop_segment(task_id);
99 65040004 : private_pop_segment(task_id) = private_push_segment(task_id);
100 65040004 : private_push_segment(task_id) = tmp;
101 194205821 : } else if (!StealPopSegmentFromGlobal(task_id)) {
102 : return false;
103 : }
104 73491679 : bool success = private_pop_segment(task_id)->Pop(entry);
105 : USE(success);
106 : DCHECK(success);
107 : }
108 : return true;
109 : }
110 :
111 : size_t LocalPushSegmentSize(int task_id) {
112 58291408 : return private_push_segment(task_id)->Size();
113 : }
114 :
115 : bool IsLocalEmpty(int task_id) {
116 7555065 : return private_pop_segment(task_id)->IsEmpty() &&
117 7555065 : private_push_segment(task_id)->IsEmpty();
118 : }
119 :
120 : bool IsGlobalPoolEmpty() { return global_pool_.IsEmpty(); }
121 :
122 379578 : bool IsGlobalEmpty() {
123 3030574 : for (int i = 0; i < num_tasks_; i++) {
124 2650997 : if (!IsLocalEmpty(i)) return false;
125 : }
126 379577 : return global_pool_.IsEmpty();
127 : }
128 :
129 : size_t LocalSize(int task_id) {
130 : return private_pop_segment(task_id)->Size() +
131 : private_push_segment(task_id)->Size();
132 : }
133 :
134 : // Clears all segments. Frees the global segment pool.
135 : //
136 : // Assumes that no other tasks are running.
137 111765 : void Clear() {
138 1005885 : for (int i = 0; i < num_tasks_; i++) {
139 894120 : private_pop_segment(i)->Clear();
140 894120 : private_push_segment(i)->Clear();
141 : }
142 111765 : global_pool_.Clear();
143 111765 : }
144 :
145 : // Calls the specified callback on each element of the deques and replaces
146 : // the element with the result of the callback.
147 : // The signature of the callback is
148 : // bool Callback(EntryType old, EntryType* new).
149 : // If the callback returns |false| then the element is removed from the
150 : // worklist. Otherwise the |new| entry is updated.
151 : //
152 : // Assumes that no other tasks are running.
153 : template <typename Callback>
154 6461 : void Update(Callback callback) {
155 58148 : for (int i = 0; i < num_tasks_; i++) {
156 51688 : private_pop_segment(i)->Update(callback);
157 51688 : private_push_segment(i)->Update(callback);
158 : }
159 6461 : global_pool_.Update(callback);
160 6461 : }
161 :
162 : template <typename Callback>
163 : void IterateGlobalPool(Callback callback) {
164 0 : global_pool_.Iterate(callback);
165 : }
166 :
167 926093 : void FlushToGlobal(int task_id) {
168 : PublishPushSegmentToGlobal(task_id);
169 : PublishPopSegmentToGlobal(task_id);
170 926110 : }
171 :
172 80914 : void MergeGlobalPool(Worklist* other) {
173 80914 : auto pair = other->global_pool_.Extract();
174 80914 : global_pool_.MergeList(pair.first, pair.second);
175 80914 : }
176 :
177 : private:
178 : FRIEND_TEST(WorkListTest, SegmentCreate);
179 : FRIEND_TEST(WorkListTest, SegmentPush);
180 : FRIEND_TEST(WorkListTest, SegmentPushPop);
181 : FRIEND_TEST(WorkListTest, SegmentIsEmpty);
182 : FRIEND_TEST(WorkListTest, SegmentIsFull);
183 : FRIEND_TEST(WorkListTest, SegmentClear);
184 : FRIEND_TEST(WorkListTest, SegmentFullPushFails);
185 : FRIEND_TEST(WorkListTest, SegmentEmptyPopFails);
186 : FRIEND_TEST(WorkListTest, SegmentUpdateFalse);
187 : FRIEND_TEST(WorkListTest, SegmentUpdate);
188 :
189 : class Segment {
190 : public:
191 : static const size_t kCapacity = kSegmentCapacity;
192 :
193 90021662 : Segment() : index_(0) {}
194 :
195 819443660 : bool Push(EntryType entry) {
196 819443853 : if (IsFull()) return false;
197 811045292 : entries_[index_++] = entry;
198 : return true;
199 : }
200 :
201 1056308402 : bool Pop(EntryType* entry) {
202 1056308403 : if (IsEmpty()) return false;
203 798066271 : *entry = entries_[--index_];
204 : return true;
205 : }
206 :
207 : size_t Size() const { return index_; }
208 10164437 : bool IsEmpty() const { return index_ == 0; }
209 2 : bool IsFull() const { return index_ == kCapacity; }
210 1788240 : void Clear() { index_ = 0; }
211 :
212 : template <typename Callback>
213 260655 : void Update(Callback callback) {
214 : size_t new_index = 0;
215 10307794 : for (size_t i = 0; i < index_; i++) {
216 10047201 : if (callback(entries_[i], &entries_[new_index])) {
217 3831478 : new_index++;
218 : }
219 : }
220 260690 : index_ = new_index;
221 260655 : }
222 :
223 : template <typename Callback>
224 : void Iterate(Callback callback) const {
225 0 : for (size_t i = 0; i < index_; i++) {
226 0 : callback(entries_[i]);
227 : }
228 : }
229 :
230 8453832 : Segment* next() const { return next_; }
231 8619051 : void set_next(Segment* segment) { next_ = segment; }
232 :
233 : private:
234 : Segment* next_;
235 : size_t index_;
236 : EntryType entries_[kCapacity];
237 : };
238 :
239 : struct PrivateSegmentHolder {
240 : Segment* private_push_segment;
241 : Segment* private_pop_segment;
242 : char cache_line_padding[64];
243 : };
244 :
245 379567 : class GlobalPool {
246 : public:
247 389371 : GlobalPool() : top_(nullptr) {}
248 :
249 : V8_INLINE void Push(Segment* segment) {
250 8583971 : base::LockGuard<base::Mutex> guard(&lock_);
251 8584748 : segment->set_next(top_);
252 8584742 : set_top(segment);
253 : }
254 :
255 : V8_INLINE bool Pop(Segment** segment) {
256 8452543 : base::LockGuard<base::Mutex> guard(&lock_);
257 8454215 : if (top_ != nullptr) {
258 : *segment = top_;
259 8453832 : set_top(top_->next());
260 : return true;
261 : }
262 8454214 : return false;
263 : }
264 :
265 : V8_INLINE bool IsEmpty() {
266 196488270 : return base::AsAtomicPointer::Relaxed_Load(&top_) == nullptr;
267 : }
268 :
269 111765 : void Clear() {
270 111765 : base::LockGuard<base::Mutex> guard(&lock_);
271 145441 : Segment* current = top_;
272 257206 : while (current != nullptr) {
273 : Segment* tmp = current;
274 : current = current->next();
275 33676 : delete tmp;
276 : }
277 : set_top(nullptr);
278 111765 : }
279 :
280 : // See Worklist::Update.
281 : template <typename Callback>
282 6461 : void Update(Callback callback) {
283 6461 : base::LockGuard<base::Mutex> guard(&lock_);
284 : Segment* prev = nullptr;
285 412648 : Segment* current = top_;
286 170235 : while (current != nullptr) {
287 157311 : current->Update(callback);
288 157313 : if (current->IsEmpty()) {
289 91561 : if (prev == nullptr) {
290 69455 : top_ = current->next();
291 : } else {
292 : prev->set_next(current->next());
293 : }
294 : Segment* tmp = current;
295 : current = current->next();
296 91562 : delete tmp;
297 : } else {
298 : prev = current;
299 : current = current->next();
300 : }
301 : }
302 6461 : }
303 :
304 : // See Worklist::Iterate.
305 : template <typename Callback>
306 0 : void Iterate(Callback callback) {
307 0 : base::LockGuard<base::Mutex> guard(&lock_);
308 0 : for (Segment* current = top_; current != nullptr;
309 : current = current->next()) {
310 : current->Iterate(callback);
311 : }
312 0 : }
313 :
314 80914 : std::pair<Segment*, Segment*> Extract() {
315 : Segment* top = nullptr;
316 : {
317 80914 : base::LockGuard<base::Mutex> guard(&lock_);
318 80914 : if (top_ == nullptr) return std::make_pair(nullptr, nullptr);
319 : top = top_;
320 : set_top(nullptr);
321 : }
322 : Segment* end = top;
323 12202 : while (end->next() != nullptr) end = end->next();
324 : return std::make_pair(top, end);
325 : }
326 :
327 80914 : void MergeList(Segment* start, Segment* end) {
328 161828 : if (start == nullptr) return;
329 : {
330 12202 : base::LockGuard<base::Mutex> guard(&lock_);
331 12202 : end->set_next(top_);
332 : set_top(start);
333 : }
334 : }
335 :
336 : private:
337 17037704 : void set_top(Segment* segment) {
338 17173873 : base::AsAtomicPointer::Relaxed_Store(&top_, segment);
339 17037704 : }
340 :
341 : base::Mutex lock_;
342 : Segment* top_;
343 : };
344 :
345 : V8_INLINE Segment*& private_push_segment(int task_id) {
346 : return private_segments_[task_id].private_push_segment;
347 : }
348 :
349 : V8_INLINE Segment*& private_pop_segment(int task_id) {
350 : return private_segments_[task_id].private_pop_segment;
351 : }
352 :
353 : V8_INLINE void PublishPushSegmentToGlobal(int task_id) {
354 9240483 : if (!private_push_segment(task_id)->IsEmpty()) {
355 8583970 : global_pool_.Push(private_push_segment(task_id));
356 8584329 : private_push_segment(task_id) = NewSegment();
357 : }
358 : }
359 :
360 : V8_INLINE void PublishPopSegmentToGlobal(int task_id) {
361 926143 : if (!private_pop_segment(task_id)->IsEmpty()) {
362 1 : global_pool_.Push(private_pop_segment(task_id));
363 1 : private_pop_segment(task_id) = NewSegment();
364 : }
365 : }
366 :
367 : V8_INLINE bool StealPopSegmentFromGlobal(int task_id) {
368 194204204 : if (global_pool_.IsEmpty()) return false;
369 : Segment* new_segment = nullptr;
370 16906702 : if (global_pool_.Pop(&new_segment)) {
371 8453777 : delete private_pop_segment(task_id);
372 8453778 : private_pop_segment(task_id) = new_segment;
373 : return true;
374 : }
375 : return false;
376 : }
377 :
378 : V8_INLINE Segment* NewSegment() {
379 : // Bottleneck for filtering in crash dumps.
380 14043413 : return new Segment();
381 : }
382 :
383 : PrivateSegmentHolder private_segments_[kMaxNumTasks];
384 : GlobalPool global_pool_;
385 : int num_tasks_;
386 : };
387 :
388 : } // namespace internal
389 : } // namespace v8
390 :
391 : #endif // V8_HEAP_WORKLIST_
|
