worklist.h 11.8 KB
Newer Older
1 2 3 4
// 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.

5 6
#ifndef V8_HEAP_WORKLIST_H_
#define V8_HEAP_WORKLIST_H_
7 8

#include <cstddef>
9
#include <utility>
10

11
#include "src/base/atomic-utils.h"
12 13 14 15 16 17 18 19
#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 {

20
// A concurrent worklist based on segments. Each tasks gets private
21 22 23 24 25 26
// 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.
27
template <typename EntryType, int SEGMENT_SIZE>
28
class Worklist {
29
 public:
30 31
  class View {
   public:
32
    View(Worklist<EntryType, SEGMENT_SIZE>* worklist, int task_id)
33 34
        : worklist_(worklist), task_id_(task_id) {}

35 36
    // Pushes an entry onto the worklist.
    bool Push(EntryType entry) { return worklist_->Push(task_id_, entry); }
37

38 39
    // Pops an entry from the worklist.
    bool Pop(EntryType* entry) { return worklist_->Pop(task_id_, entry); }
40 41 42 43 44 45

    // 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.
46
    bool IsEmpty() { return worklist_->IsEmpty(); }
47

48 49
    bool IsGlobalPoolEmpty() { return worklist_->IsGlobalPoolEmpty(); }

50 51 52 53
    size_t LocalPushSegmentSize() {
      return worklist_->LocalPushSegmentSize(task_id_);
    }

54
   private:
55
    Worklist<EntryType, SEGMENT_SIZE>* worklist_;
56 57 58
    int task_id_;
  };

59
  static const int kMaxNumTasks = 8;
60
  static const size_t kSegmentCapacity = SEGMENT_SIZE;
61

62 63 64 65
  Worklist() : Worklist(kMaxNumTasks) {}

  explicit Worklist(int num_tasks) : num_tasks_(num_tasks) {
    for (int i = 0; i < num_tasks_; i++) {
66 67
      private_push_segment(i) = NewSegment();
      private_pop_segment(i) = NewSegment();
68 69 70
    }
  }

71
  ~Worklist() {
72
    CHECK(IsEmpty());
73
    for (int i = 0; i < num_tasks_; i++) {
74 75 76 77
      DCHECK_NOT_NULL(private_push_segment(i));
      DCHECK_NOT_NULL(private_pop_segment(i));
      delete private_push_segment(i);
      delete private_pop_segment(i);
78 79 80
    }
  }

81 82 83 84 85 86 87 88 89
  // 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_);
  }

90
  bool Push(int task_id, EntryType entry) {
91
    DCHECK_LT(task_id, num_tasks_);
92 93
    DCHECK_NOT_NULL(private_push_segment(task_id));
    if (!private_push_segment(task_id)->Push(entry)) {
94
      PublishPushSegmentToGlobal(task_id);
95
      bool success = private_push_segment(task_id)->Push(entry);
96 97 98 99 100 101
      USE(success);
      DCHECK(success);
    }
    return true;
  }

102
  bool Pop(int task_id, EntryType* entry) {
103
    DCHECK_LT(task_id, num_tasks_);
104 105 106 107 108 109
    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;
110 111
      } else if (!StealPopSegmentFromGlobal(task_id)) {
        return false;
112
      }
113
      bool success = private_pop_segment(task_id)->Pop(entry);
114 115 116 117 118 119
      USE(success);
      DCHECK(success);
    }
    return true;
  }

120
  size_t LocalPushSegmentSize(int task_id) {
121
    return private_push_segment(task_id)->Size();
122 123
  }

124
  bool IsLocalEmpty(int task_id) {
125 126
    return private_pop_segment(task_id)->IsEmpty() &&
           private_push_segment(task_id)->IsEmpty();
127 128
  }

129
  bool IsGlobalPoolEmpty() { return global_pool_.IsEmpty(); }
130

131
  bool IsEmpty() {
132 133 134 135 136
    if (!AreLocalsEmpty()) return false;
    return global_pool_.IsEmpty();
  }

  bool AreLocalsEmpty() {
137
    for (int i = 0; i < num_tasks_; i++) {
138 139
      if (!IsLocalEmpty(i)) return false;
    }
140
    return true;
141 142
  }

143
  size_t LocalSize(int task_id) {
144 145
    return private_pop_segment(task_id)->Size() +
           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 154
      private_pop_segment(i)->Clear();
      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 161 162 163 164
  // 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.
165 166
  //
  // Assumes that no other tasks are running.
167 168
  template <typename Callback>
  void Update(Callback callback) {
169
    for (int i = 0; i < num_tasks_; i++) {
170 171
      private_pop_segment(i)->Update(callback);
      private_push_segment(i)->Update(callback);
172
    }
173
    global_pool_.Update(callback);
174 175
  }

176 177 178 179 180 181 182 183 184 185 186 187 188 189
  // 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);
  }

190 191
  template <typename Callback>
  void IterateGlobalPool(Callback callback) {
192
    global_pool_.Iterate(callback);
193 194
  }

195 196 197 198 199
  void FlushToGlobal(int task_id) {
    PublishPushSegmentToGlobal(task_id);
    PublishPopSegmentToGlobal(task_id);
  }

200 201 202 203 204
  void MergeGlobalPool(Worklist* other) {
    auto pair = other->global_pool_.Extract();
    global_pool_.MergeList(pair.first, pair.second);
  }

205
 private:
206 207 208 209 210 211 212 213 214 215
  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);
216 217 218

  class Segment {
   public:
219
    static const size_t kCapacity = kSegmentCapacity;
220 221 222

    Segment() : index_(0) {}

223
    bool Push(EntryType entry) {
224
      if (IsFull()) return false;
225
      entries_[index_++] = entry;
226 227 228
      return true;
    }

229
    bool Pop(EntryType* entry) {
230
      if (IsEmpty()) return false;
231
      *entry = entries_[--index_];
232 233 234
      return true;
    }

235 236 237
    size_t Size() const { return index_; }
    bool IsEmpty() const { return index_ == 0; }
    bool IsFull() const { return index_ == kCapacity; }
238 239
    void Clear() { index_ = 0; }

240 241 242 243
    template <typename Callback>
    void Update(Callback callback) {
      size_t new_index = 0;
      for (size_t i = 0; i < index_; i++) {
244 245
        if (callback(entries_[i], &entries_[new_index])) {
          new_index++;
246 247 248 249 250
        }
      }
      index_ = new_index;
    }

251
    template <typename Callback>
252
    void Iterate(Callback callback) const {
253 254 255 256 257
      for (size_t i = 0; i < index_; i++) {
        callback(entries_[i]);
      }
    }

258 259 260
    Segment* next() const { return next_; }
    void set_next(Segment* segment) { next_ = segment; }

261
   private:
262
    Segment* next_;
263
    size_t index_;
264
    EntryType entries_[kCapacity];
265 266
  };

267 268 269 270 271 272
  struct PrivateSegmentHolder {
    Segment* private_push_segment;
    Segment* private_pop_segment;
    char cache_line_padding[64];
  };

273 274 275 276
  class GlobalPool {
   public:
    GlobalPool() : top_(nullptr) {}

277 278 279 280 281 282 283
    // Swaps contents, not thread safe.
    void Swap(GlobalPool& other) {
      Segment* temp = top_;
      set_top(other.top_);
      other.set_top(temp);
    }

284 285 286
    V8_INLINE void Push(Segment* segment) {
      base::LockGuard<base::Mutex> guard(&lock_);
      segment->set_next(top_);
287
      set_top(segment);
288 289 290 291 292 293
    }

    V8_INLINE bool Pop(Segment** segment) {
      base::LockGuard<base::Mutex> guard(&lock_);
      if (top_ != nullptr) {
        *segment = top_;
294
        set_top(top_->next());
295 296 297 298 299 300
        return true;
      }
      return false;
    }

    V8_INLINE bool IsEmpty() {
301
      return base::AsAtomicPointer::Relaxed_Load(&top_) == nullptr;
302 303 304 305 306 307 308 309 310 311
    }

    void Clear() {
      base::LockGuard<base::Mutex> guard(&lock_);
      Segment* current = top_;
      while (current != nullptr) {
        Segment* tmp = current;
        current = current->next();
        delete tmp;
      }
312
      set_top(nullptr);
313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348
    }

    // See Worklist::Update.
    template <typename Callback>
    void Update(Callback callback) {
      base::LockGuard<base::Mutex> guard(&lock_);
      Segment* prev = nullptr;
      Segment* current = top_;
      while (current != nullptr) {
        current->Update(callback);
        if (current->IsEmpty()) {
          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();
        }
      }
    }

    // See Worklist::Iterate.
    template <typename Callback>
    void Iterate(Callback callback) {
      base::LockGuard<base::Mutex> guard(&lock_);
      for (Segment* current = top_; current != nullptr;
           current = current->next()) {
        current->Iterate(callback);
      }
    }

349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370
    std::pair<Segment*, Segment*> Extract() {
      Segment* top = nullptr;
      {
        base::LockGuard<base::Mutex> guard(&lock_);
        if (top_ == nullptr) return std::make_pair(nullptr, nullptr);
        top = top_;
        set_top(nullptr);
      }
      Segment* end = top;
      while (end->next() != nullptr) end = end->next();
      return std::make_pair(top, end);
    }

    void MergeList(Segment* start, Segment* end) {
      if (start == nullptr) return;
      {
        base::LockGuard<base::Mutex> guard(&lock_);
        end->set_next(top_);
        set_top(start);
      }
    }

371
   private:
372
    void set_top(Segment* segment) {
373 374
      base::AsAtomicPointer::Relaxed_Store(&top_, segment);
    }
375

376 377 378 379
    base::Mutex lock_;
    Segment* top_;
  };

380 381 382 383 384 385 386 387
  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;
  }

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 405 406 407 408 409 410
    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;
411 412
  }

413 414 415 416 417
  V8_INLINE Segment* NewSegment() {
    // Bottleneck for filtering in crash dumps.
    return new Segment();
  }

418
  PrivateSegmentHolder private_segments_[kMaxNumTasks];
419
  GlobalPool global_pool_;
420
  int num_tasks_;
421 422 423 424 425
};

}  // namespace internal
}  // namespace v8

426
#endif  // V8_HEAP_WORKLIST_H_