Home | History | Annotate | Download | only in heap 
      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         : worklist_(worklist), task_id_(task_id) {}
     34 
     35     // Pushes an entry onto the worklist.
     36     bool Push(EntryType entry) { return worklist_->Push(task_id_, entry); }
     37 
     38     // Pops an entry from the worklist.
     39     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   Worklist() : Worklist(kMaxNumTasks) {}
     63 
     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 
     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.
     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 
     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 
    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 
    120   size_t LocalPushSegmentSize(int task_id) {
    121     return private_push_segment(task_id)->Size();
    122   }
    123 
    124   bool IsLocalEmpty(int task_id) {
    125     return private_pop_segment(task_id)->IsEmpty() &&
    126            private_push_segment(task_id)->IsEmpty();
    127   }
    128 
    129   bool IsGlobalPoolEmpty() { return global_pool_.IsEmpty(); }
    130 
    131   bool IsEmpty() {
    132     if (!AreLocalsEmpty()) return false;
    133     return global_pool_.IsEmpty();
    134   }
    135 
    136   bool AreLocalsEmpty() {
    137     for (int i = 0; i < num_tasks_; i++) {
    138       if (!IsLocalEmpty(i)) return false;
    139     }
    140     return true;
    141   }
    142 
    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.
    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>
    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>
    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>
    191   void IterateGlobalPool(Callback callback) {
    192     global_pool_.Iterate(callback);
    193   }
    194 
    195   void FlushToGlobal(int task_id) {
    196     PublishPushSegmentToGlobal(task_id);
    197     PublishPopSegmentToGlobal(task_id);
    198   }
    199 
    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 
    221     Segment() : index_(0) {}
    222 
    223     bool Push(EntryType entry) {
    224       if (IsFull()) return false;
    225       entries_[index_++] = entry;
    226       return true;
    227     }
    228 
    229     bool Pop(EntryType* entry) {
    230       if (IsEmpty()) return false;
    231       *entry = entries_[--index_];
    232       return true;
    233     }
    234 
    235     size_t Size() const { return index_; }
    236     bool IsEmpty() const { return index_ == 0; }
    237     bool IsFull() const { return index_ == kCapacity; }
    238     void Clear() { index_ = 0; }
    239 
    240     template <typename 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>
    252     void Iterate(Callback callback) const {
    253       for (size_t i = 0; i < index_; i++) {
    254         callback(entries_[i]);
    255       }
    256     }
    257 
    258     Segment* next() const { return next_; }
    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:
    275     GlobalPool() : top_(nullptr) {}
    276 
    277     // Swaps contents, not thread safe.
    278     void Swap(GlobalPool& other) {
    279       Segment* temp = top_;
    280       set_top(other.top_);
    281       other.set_top(temp);
    282     }
    283 
    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 
    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 
    300     V8_INLINE bool IsEmpty() {
    301       return base::AsAtomicPointer::Relaxed_Load(&top_) == nullptr;
    302     }
    303 
    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>
    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>
    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 
    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 
    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:
    372     void set_top(Segment* segment) {
    373       base::AsAtomicPointer::Relaxed_Store(&top_, segment);
    374     }
    375 
    376     base::Mutex lock_;
    377     Segment* top_;
    378   };
    379 
    380   V8_INLINE Segment*& private_push_segment(int task_id) {
    381     return private_segments_[task_id].private_push_segment;
    382   }
    383 
    384   V8_INLINE Segment*& private_pop_segment(int task_id) {
    385     return private_segments_[task_id].private_pop_segment;
    386   }
    387 
    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 
    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 
    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 
    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