// Copyright 2017 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef V8_HEAP_WORKLIST_H_ #define V8_HEAP_WORKLIST_H_ #include <cstddef> #include <utility> #include "src/base/atomic-utils.h" #include "src/base/logging.h" #include "src/base/macros.h" #include "src/base/platform/mutex.h" #include "testing/gtest/include/gtest/gtest_prod.h" // nogncheck namespace v8 { namespace internal { // A concurrent worklist based on segments. Each tasks gets private // push and pop segments. Empty pop segments are swapped with their // corresponding push segments. Full push segments are published to a global // pool of segments and replaced with empty segments. // // Work stealing is best effort, i.e., there is no way to inform other tasks // of the need of items. template <typename EntryType, int SEGMENT_SIZE> class Worklist { public: class View { public: View(Worklist<EntryType, SEGMENT_SIZE>* worklist, int task_id) : worklist_(worklist), task_id_(task_id) {} // Pushes an entry onto the worklist. bool Push(EntryType entry) { return worklist_->Push(task_id_, entry); } // Pops an entry from the worklist. bool Pop(EntryType* entry) { return worklist_->Pop(task_id_, entry); } // Returns true if the local portion of the worklist is empty. bool IsLocalEmpty() { return worklist_->IsLocalEmpty(task_id_); } // Returns true if the worklist is empty. Can only be used from the main // thread without concurrent access. bool IsEmpty() { return worklist_->IsEmpty(); } bool IsGlobalPoolEmpty() { return worklist_->IsGlobalPoolEmpty(); } size_t LocalPushSegmentSize() { return worklist_->LocalPushSegmentSize(task_id_); } void FlushToGlobal() { worklist_->FlushToGlobal(task_id_); } private: Worklist<EntryType, SEGMENT_SIZE>* worklist_; int task_id_; }; static const int kMaxNumTasks = 8; static const size_t kSegmentCapacity = SEGMENT_SIZE; Worklist() : Worklist(kMaxNumTasks) {} explicit Worklist(int num_tasks) : num_tasks_(num_tasks) { DCHECK_LE(num_tasks, kMaxNumTasks); for (int i = 0; i < num_tasks_; i++) { private_push_segment(i) = NewSegment(); private_pop_segment(i) = NewSegment(); } } ~Worklist() { CHECK(IsEmpty()); for (int i = 0; i < num_tasks_; i++) { DCHECK_NOT_NULL(private_push_segment(i)); DCHECK_NOT_NULL(private_pop_segment(i)); delete private_push_segment(i); delete private_pop_segment(i); } } // Swaps content with the given worklist. Local buffers need to // be empty, not thread safe. void Swap(Worklist<EntryType, SEGMENT_SIZE>& other) { CHECK(AreLocalsEmpty()); CHECK(other.AreLocalsEmpty()); global_pool_.Swap(other.global_pool_); } bool Push(int task_id, EntryType entry) { DCHECK_LT(task_id, num_tasks_); DCHECK_NOT_NULL(private_push_segment(task_id)); if (!private_push_segment(task_id)->Push(entry)) { PublishPushSegmentToGlobal(task_id); bool success = private_push_segment(task_id)->Push(entry); USE(success); DCHECK(success); } return true; } bool Pop(int task_id, EntryType* entry) { DCHECK_LT(task_id, num_tasks_); DCHECK_NOT_NULL(private_pop_segment(task_id)); if (!private_pop_segment(task_id)->Pop(entry)) { if (!private_push_segment(task_id)->IsEmpty()) { Segment* tmp = private_pop_segment(task_id); private_pop_segment(task_id) = private_push_segment(task_id); private_push_segment(task_id) = tmp; } else if (!StealPopSegmentFromGlobal(task_id)) { return false; } bool success = private_pop_segment(task_id)->Pop(entry); USE(success); DCHECK(success); } return true; } size_t LocalPushSegmentSize(int task_id) { return private_push_segment(task_id)->Size(); } bool IsLocalEmpty(int task_id) { return private_pop_segment(task_id)->IsEmpty() && private_push_segment(task_id)->IsEmpty(); } bool IsGlobalPoolEmpty() { return global_pool_.IsEmpty(); } bool IsEmpty() { if (!AreLocalsEmpty()) return false; return global_pool_.IsEmpty(); } bool AreLocalsEmpty() { for (int i = 0; i < num_tasks_; i++) { if (!IsLocalEmpty(i)) return false; } return true; } size_t LocalSize(int task_id) { return private_pop_segment(task_id)->Size() + private_push_segment(task_id)->Size(); } // Thread-safe but may return an outdated result. size_t GlobalPoolSize() const { return global_pool_.Size(); } // Clears all segments. Frees the global segment pool. // // Assumes that no other tasks are running. void Clear() { for (int i = 0; i < num_tasks_; i++) { private_pop_segment(i)->Clear(); private_push_segment(i)->Clear(); } global_pool_.Clear(); } // Calls the specified callback on each element of the deques and replaces // the element with the result of the callback. // The signature of the callback is // bool Callback(EntryType old, EntryType* new). // If the callback returns |false| then the element is removed from the // worklist. Otherwise the |new| entry is updated. // // Assumes that no other tasks are running. template <typename Callback> void Update(Callback callback) { for (int i = 0; i < num_tasks_; i++) { private_pop_segment(i)->Update(callback); private_push_segment(i)->Update(callback); } global_pool_.Update(callback); } // Calls the specified callback on each element of the deques. // The signature of the callback is: // void Callback(EntryType entry). // // Assumes that no other tasks are running. template <typename Callback> void Iterate(Callback callback) { for (int i = 0; i < num_tasks_; i++) { private_pop_segment(i)->Iterate(callback); private_push_segment(i)->Iterate(callback); } global_pool_.Iterate(callback); } template <typename Callback> void IterateGlobalPool(Callback callback) { global_pool_.Iterate(callback); } void FlushToGlobal(int task_id) { PublishPushSegmentToGlobal(task_id); PublishPopSegmentToGlobal(task_id); } void MergeGlobalPool(Worklist* other) { global_pool_.Merge(&other->global_pool_); } private: FRIEND_TEST(WorkListTest, SegmentCreate); FRIEND_TEST(WorkListTest, SegmentPush); FRIEND_TEST(WorkListTest, SegmentPushPop); FRIEND_TEST(WorkListTest, SegmentIsEmpty); FRIEND_TEST(WorkListTest, SegmentIsFull); FRIEND_TEST(WorkListTest, SegmentClear); FRIEND_TEST(WorkListTest, SegmentFullPushFails); FRIEND_TEST(WorkListTest, SegmentEmptyPopFails); FRIEND_TEST(WorkListTest, SegmentUpdateFalse); FRIEND_TEST(WorkListTest, SegmentUpdate); class Segment { public: static const size_t kCapacity = kSegmentCapacity; Segment() : index_(0) {} bool Push(EntryType entry) { if (IsFull()) return false; entries_[index_++] = entry; return true; } bool Pop(EntryType* entry) { if (IsEmpty()) return false; *entry = entries_[--index_]; return true; } size_t Size() const { return index_; } bool IsEmpty() const { return index_ == 0; } bool IsFull() const { return index_ == kCapacity; } void Clear() { index_ = 0; } template <typename Callback> void Update(Callback callback) { size_t new_index = 0; for (size_t i = 0; i < index_; i++) { if (callback(entries_[i], &entries_[new_index])) { new_index++; } } index_ = new_index; } template <typename Callback> void Iterate(Callback callback) const { for (size_t i = 0; i < index_; i++) { callback(entries_[i]); } } Segment* next() const { return next_; } void set_next(Segment* segment) { next_ = segment; } private: Segment* next_; size_t index_; EntryType entries_[kCapacity]; }; struct PrivateSegmentHolder { Segment* private_push_segment; Segment* private_pop_segment; char cache_line_padding[64]; }; class GlobalPool { public: GlobalPool() : top_(nullptr) {} // Swaps contents, not thread safe. void Swap(GlobalPool& other) { Segment* temp = top_; set_top(other.top_); other.set_top(temp); size_t other_size = other.size_.exchange( size_.load(std::memory_order_relaxed), std::memory_order_relaxed); size_.store(other_size, std::memory_order_relaxed); } V8_INLINE void Push(Segment* segment) { base::MutexGuard guard(&lock_); segment->set_next(top_); set_top(segment); size_.fetch_add(1, std::memory_order_relaxed); } V8_INLINE bool Pop(Segment** segment) { base::MutexGuard guard(&lock_); if (top_ != nullptr) { DCHECK_LT(0U, size_); size_.fetch_sub(1, std::memory_order_relaxed); *segment = top_; set_top(top_->next()); return true; } return false; } V8_INLINE bool IsEmpty() { return base::AsAtomicPointer::Relaxed_Load(&top_) == nullptr; } V8_INLINE size_t Size() const { // It is safe to read |size_| without a lock since this variable is // atomic, keeping in mind that threads may not immediately see the new // value when it is updated. return size_.load(std::memory_order_relaxed); } void Clear() { base::MutexGuard guard(&lock_); size_.store(0, std::memory_order_relaxed); Segment* current = top_; while (current != nullptr) { Segment* tmp = current; current = current->next(); delete tmp; } set_top(nullptr); } // See Worklist::Update. template <typename Callback> void Update(Callback callback) { base::MutexGuard guard(&lock_); Segment* prev = nullptr; Segment* current = top_; size_t num_deleted = 0; while (current != nullptr) { current->Update(callback); if (current->IsEmpty()) { DCHECK_LT(0U, size_); ++num_deleted; if (prev == nullptr) { top_ = current->next(); } else { prev->set_next(current->next()); } Segment* tmp = current; current = current->next(); delete tmp; } else { prev = current; current = current->next(); } } size_.fetch_sub(num_deleted, std::memory_order_relaxed); } // See Worklist::Iterate. template <typename Callback> void Iterate(Callback callback) { base::MutexGuard guard(&lock_); for (Segment* current = top_; current != nullptr; current = current->next()) { current->Iterate(callback); } } void Merge(GlobalPool* other) { Segment* top = nullptr; size_t other_size = 0; { base::MutexGuard guard(&other->lock_); if (!other->top_) return; top = other->top_; other_size = other->size_.load(std::memory_order_relaxed); other->size_.store(0, std::memory_order_relaxed); other->set_top(nullptr); } // It's safe to iterate through these segments because the top was // extracted from |other|. Segment* end = top; while (end->next()) end = end->next(); { base::MutexGuard guard(&lock_); size_.fetch_add(other_size, std::memory_order_relaxed); end->set_next(top_); set_top(top); } } private: void set_top(Segment* segment) { base::AsAtomicPointer::Relaxed_Store(&top_, segment); } base::Mutex lock_; Segment* top_; std::atomic<size_t> size_{0}; }; V8_INLINE Segment*& private_push_segment(int task_id) { return private_segments_[task_id].private_push_segment; } V8_INLINE Segment*& private_pop_segment(int task_id) { return private_segments_[task_id].private_pop_segment; } V8_INLINE void PublishPushSegmentToGlobal(int task_id) { if (!private_push_segment(task_id)->IsEmpty()) { global_pool_.Push(private_push_segment(task_id)); private_push_segment(task_id) = NewSegment(); } } V8_INLINE void PublishPopSegmentToGlobal(int task_id) { if (!private_pop_segment(task_id)->IsEmpty()) { global_pool_.Push(private_pop_segment(task_id)); private_pop_segment(task_id) = NewSegment(); } } V8_INLINE bool StealPopSegmentFromGlobal(int task_id) { if (global_pool_.IsEmpty()) return false; Segment* new_segment = nullptr; if (global_pool_.Pop(&new_segment)) { delete private_pop_segment(task_id); private_pop_segment(task_id) = new_segment; return true; } return false; } V8_INLINE Segment* NewSegment() { // Bottleneck for filtering in crash dumps. return new Segment(); } PrivateSegmentHolder private_segments_[kMaxNumTasks]; GlobalPool global_pool_; int num_tasks_; }; } // namespace internal } // namespace v8 #endif // V8_HEAP_WORKLIST_H_