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