worklist.h 14.3 KB
Newer Older
Omer Katz's avatar
Omer Katz committed
1 2 3 4
// Copyright 2020 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_BASE_WORKLIST_H_
#define V8_HEAP_BASE_WORKLIST_H_
Omer Katz's avatar
Omer Katz committed
7 8 9 10 11 12 13 14 15

#include <cstddef>
#include <utility>

#include "src/base/atomic-utils.h"
#include "src/base/logging.h"
#include "src/base/platform/mutex.h"
#include "testing/gtest/include/gtest/gtest_prod.h"  // nogncheck

16 17
namespace heap {
namespace base {
Omer Katz's avatar
Omer Katz committed
18

19 20 21
namespace internal {
class V8_EXPORT_PRIVATE SegmentBase {
 public:
22
  static SegmentBase* GetSentinelSegmentAddress();
23 24 25 26 27 28 29 30 31 32 33 34 35 36

  explicit SegmentBase(uint16_t capacity) : capacity_(capacity) {}

  size_t Size() const { return index_; }
  bool IsEmpty() const { return index_ == 0; }
  bool IsFull() const { return index_ == capacity_; }
  void Clear() { index_ = 0; }

 protected:
  const uint16_t capacity_;
  uint16_t index_ = 0;
};
}  // namespace internal

37 38 39 40
// A global marking worklist that is similar the existing Worklist
// but does not reserve space and keep track of the local segments.
// Eventually this will replace Worklist after all its current uses
// are migrated.
41
template <typename EntryType, uint16_t SegmentSize>
Omer Katz's avatar
Omer Katz committed
42 43
class Worklist {
 public:
44 45 46
  static const int kSegmentSize = SegmentSize;
  class Segment;
  class Local;
Omer Katz's avatar
Omer Katz committed
47

48 49
  Worklist() = default;
  ~Worklist() { CHECK(IsEmpty()); }
Omer Katz's avatar
Omer Katz committed
50

51 52
  void Push(Segment* segment);
  bool Pop(Segment** segment);
Omer Katz's avatar
Omer Katz committed
53

54
  // Returns true if the list of segments is empty.
55
  bool IsEmpty() const;
56
  // Returns the number of segments in the list.
57
  size_t Size() const;
Omer Katz's avatar
Omer Katz committed
58

59 60 61
  // Moves the segments of the given marking worklist into this
  // marking worklist.
  void Merge(Worklist<EntryType, SegmentSize>* other);
Omer Katz's avatar
Omer Katz committed
62

63 64 65
  // Swaps the segments with the given marking worklist.
  void Swap(Worklist<EntryType, SegmentSize>* other);

66 67 68 69 70 71 72 73
  // These functions are not thread-safe. They should be called only
  // if all local marking worklists that use the current worklist have
  // been published and are empty.
  void Clear();
  template <typename Callback>
  void Update(Callback callback);
  template <typename Callback>
  void Iterate(Callback callback);
Omer Katz's avatar
Omer Katz committed
74

75 76 77
 private:
  void set_top(Segment* segment) {
    v8::base::AsAtomicPtr(&top_)->store(segment, std::memory_order_relaxed);
Omer Katz's avatar
Omer Katz committed
78 79
  }

80 81 82 83
  v8::base::Mutex lock_;
  Segment* top_ = nullptr;
  std::atomic<size_t> size_{0};
};
Omer Katz's avatar
Omer Katz committed
84

85
template <typename EntryType, uint16_t SegmentSize>
86
void Worklist<EntryType, SegmentSize>::Push(Segment* segment) {
87
  DCHECK(!segment->IsEmpty());
88 89 90 91 92 93
  v8::base::MutexGuard guard(&lock_);
  segment->set_next(top_);
  set_top(segment);
  size_.fetch_add(1, std::memory_order_relaxed);
}

94
template <typename EntryType, uint16_t SegmentSize>
95 96
bool Worklist<EntryType, SegmentSize>::Pop(Segment** segment) {
  v8::base::MutexGuard guard(&lock_);
97 98 99 100 101 102
  if (top_ == nullptr) return false;
  DCHECK_LT(0U, size_);
  size_.fetch_sub(1, std::memory_order_relaxed);
  *segment = top_;
  set_top(top_->next());
  return true;
103 104
}

105
template <typename EntryType, uint16_t SegmentSize>
106
bool Worklist<EntryType, SegmentSize>::IsEmpty() const {
107 108 109 110
  return v8::base::AsAtomicPtr(&top_)->load(std::memory_order_relaxed) ==
         nullptr;
}

111
template <typename EntryType, uint16_t SegmentSize>
112
size_t Worklist<EntryType, SegmentSize>::Size() const {
113 114 115 116 117 118
  // 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);
}

119
template <typename EntryType, uint16_t SegmentSize>
120 121 122 123 124 125 126 127 128 129 130 131
void Worklist<EntryType, SegmentSize>::Clear() {
  v8::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);
}

132
template <typename EntryType, uint16_t SegmentSize>
133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
template <typename Callback>
void Worklist<EntryType, SegmentSize>::Update(Callback callback) {
  v8::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());
Omer Katz's avatar
Omer Katz committed
148
      }
149 150 151 152 153 154
      Segment* tmp = current;
      current = current->next();
      delete tmp;
    } else {
      prev = current;
      current = current->next();
Omer Katz's avatar
Omer Katz committed
155 156
    }
  }
157 158 159
  size_.fetch_sub(num_deleted, std::memory_order_relaxed);
}

160
template <typename EntryType, uint16_t SegmentSize>
161 162 163 164 165
template <typename Callback>
void Worklist<EntryType, SegmentSize>::Iterate(Callback callback) {
  v8::base::MutexGuard guard(&lock_);
  for (Segment* current = top_; current != nullptr; current = current->next()) {
    current->Iterate(callback);
Omer Katz's avatar
Omer Katz committed
166
  }
167 168
}

169
template <typename EntryType, uint16_t SegmentSize>
170 171 172 173 174 175 176 177 178 179 180
void Worklist<EntryType, SegmentSize>::Merge(
    Worklist<EntryType, SegmentSize>* other) {
  Segment* top = nullptr;
  size_t other_size = 0;
  {
    v8::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);
Omer Katz's avatar
Omer Katz committed
181 182
  }

183 184 185 186
  // It's safe to iterate through these segments because the top was
  // extracted from |other|.
  Segment* end = top;
  while (end->next()) end = end->next();
Omer Katz's avatar
Omer Katz committed
187

188 189 190 191 192
  {
    v8::base::MutexGuard guard(&lock_);
    size_.fetch_add(other_size, std::memory_order_relaxed);
    end->set_next(top_);
    set_top(top);
Omer Katz's avatar
Omer Katz committed
193
  }
194
}
Omer Katz's avatar
Omer Katz committed
195

196 197 198 199 200 201 202 203 204 205 206
template <typename EntryType, uint16_t SegmentSize>
void Worklist<EntryType, SegmentSize>::Swap(
    Worklist<EntryType, SegmentSize>* other) {
  Segment* top = top_;
  set_top(other->top_);
  other->set_top(top);
  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);
}

207 208
template <typename EntryType, uint16_t SegmentSize>
class Worklist<EntryType, SegmentSize>::Segment : public internal::SegmentBase {
209
 public:
210
  static const uint16_t kSize = SegmentSize;
Omer Katz's avatar
Omer Katz committed
211

212 213
  void Push(EntryType entry);
  void Pop(EntryType* entry);
214

Omer Katz's avatar
Omer Katz committed
215
  template <typename Callback>
216
  void Update(Callback callback);
Omer Katz's avatar
Omer Katz committed
217
  template <typename Callback>
218
  void Iterate(Callback callback) const;
Omer Katz's avatar
Omer Katz committed
219

220 221
  Segment* next() const { return next_; }
  void set_next(Segment* segment) { next_ = segment; }
Omer Katz's avatar
Omer Katz committed
222 223

 private:
224 225
  Segment() : internal::SegmentBase(kSize) {}

226 227
  Segment* next_ = nullptr;
  EntryType entries_[kSize];
228 229 230

  friend class Worklist<EntryType, SegmentSize>::Local;

231 232 233 234 235 236 237 238
  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, SegmentUpdateFalse);
  FRIEND_TEST(WorkListTest, SegmentUpdate);
239
};
Omer Katz's avatar
Omer Katz committed
240

241 242 243
template <typename EntryType, uint16_t SegmentSize>
void Worklist<EntryType, SegmentSize>::Segment::Push(EntryType entry) {
  DCHECK(!IsFull());
244 245 246
  entries_[index_++] = entry;
}

247 248 249
template <typename EntryType, uint16_t SegmentSize>
void Worklist<EntryType, SegmentSize>::Segment::Pop(EntryType* entry) {
  DCHECK(!IsEmpty());
250 251 252
  *entry = entries_[--index_];
}

253
template <typename EntryType, uint16_t SegmentSize>
254 255 256 257 258 259
template <typename Callback>
void Worklist<EntryType, SegmentSize>::Segment::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++;
Omer Katz's avatar
Omer Katz committed
260
    }
261 262 263 264
  }
  index_ = new_index;
}

265
template <typename EntryType, uint16_t SegmentSize>
266 267 268 269 270 271 272
template <typename Callback>
void Worklist<EntryType, SegmentSize>::Segment::Iterate(
    Callback callback) const {
  for (size_t i = 0; i < index_; i++) {
    callback(entries_[i]);
  }
}
Omer Katz's avatar
Omer Katz committed
273

274
// A thread-local view of the marking worklist.
275
template <typename EntryType, uint16_t SegmentSize>
276 277 278
class Worklist<EntryType, SegmentSize>::Local {
 public:
  using ItemType = EntryType;
Omer Katz's avatar
Omer Katz committed
279

280 281 282
  Local() = default;
  explicit Local(Worklist<EntryType, SegmentSize>* worklist);
  ~Local();
Omer Katz's avatar
Omer Katz committed
283

284 285
  Local(Local&&) V8_NOEXCEPT;
  Local& operator=(Local&&) V8_NOEXCEPT;
Omer Katz's avatar
Omer Katz committed
286

287 288 289 290
  // Disable copying since having multiple copies of the same
  // local marking worklist is unsafe.
  Local(const Local&) = delete;
  Local& operator=(const Local& other) = delete;
Omer Katz's avatar
Omer Katz committed
291

292 293
  void Push(EntryType entry);
  bool Pop(EntryType* entry);
Omer Katz's avatar
Omer Katz committed
294

295 296 297
  bool IsLocalAndGlobalEmpty() const;
  bool IsLocalEmpty() const;
  bool IsGlobalEmpty() const;
Omer Katz's avatar
Omer Katz committed
298

299
  void Publish();
300
  void Merge(Worklist<EntryType, SegmentSize>::Local* other);
Omer Katz's avatar
Omer Katz committed
301

302 303 304
  bool IsEmpty() const;
  void Clear();

305
  size_t PushSegmentSize() const { return push_segment_->Size(); }
Omer Katz's avatar
Omer Katz committed
306

307 308 309 310
 private:
  void PublishPushSegment();
  void PublishPopSegment();
  bool StealPopSegment();
311

312 313 314
  Segment* NewSegment() const {
    // Bottleneck for filtering in crash dumps.
    return new Segment();
Omer Katz's avatar
Omer Katz committed
315
  }
316
  void DeleteSegment(internal::SegmentBase* segment) const {
317
    if (segment == internal::SegmentBase::GetSentinelSegmentAddress()) return;
318 319 320 321
    delete static_cast<Segment*>(segment);
  }

  inline Segment* push_segment() {
322 323
    DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(),
              push_segment_);
324 325 326
    return static_cast<Segment*>(push_segment_);
  }
  inline const Segment* push_segment() const {
327 328
    DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(),
              push_segment_);
329 330 331 332
    return static_cast<const Segment*>(push_segment_);
  }

  inline Segment* pop_segment() {
333
    DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(), pop_segment_);
334 335 336
    return static_cast<Segment*>(pop_segment_);
  }
  inline const Segment* pop_segment() const {
337
    DCHECK_NE(internal::SegmentBase::GetSentinelSegmentAddress(), pop_segment_);
338 339
    return static_cast<const Segment*>(pop_segment_);
  }
Omer Katz's avatar
Omer Katz committed
340

341
  Worklist<EntryType, SegmentSize>* worklist_ = nullptr;
342 343
  internal::SegmentBase* push_segment_ = nullptr;
  internal::SegmentBase* pop_segment_ = nullptr;
344
};
Omer Katz's avatar
Omer Katz committed
345

346
template <typename EntryType, uint16_t SegmentSize>
347 348 349
Worklist<EntryType, SegmentSize>::Local::Local(
    Worklist<EntryType, SegmentSize>* worklist)
    : worklist_(worklist),
350 351
      push_segment_(internal::SegmentBase::GetSentinelSegmentAddress()),
      pop_segment_(internal::SegmentBase::GetSentinelSegmentAddress()) {}
352

353
template <typename EntryType, uint16_t SegmentSize>
354 355 356
Worklist<EntryType, SegmentSize>::Local::~Local() {
  CHECK_IMPLIES(push_segment_, push_segment_->IsEmpty());
  CHECK_IMPLIES(pop_segment_, pop_segment_->IsEmpty());
357 358
  DeleteSegment(push_segment_);
  DeleteSegment(pop_segment_);
359 360
}

361
template <typename EntryType, uint16_t SegmentSize>
362 363 364 365 366 367 368 369 370 371
Worklist<EntryType, SegmentSize>::Local::Local(
    Worklist<EntryType, SegmentSize>::Local&& other) V8_NOEXCEPT {
  worklist_ = other.worklist_;
  push_segment_ = other.push_segment_;
  pop_segment_ = other.pop_segment_;
  other.worklist_ = nullptr;
  other.push_segment_ = nullptr;
  other.pop_segment_ = nullptr;
}

372
template <typename EntryType, uint16_t SegmentSize>
373 374 375 376 377 378 379 380 381 382 383 384 385
typename Worklist<EntryType, SegmentSize>::Local&
Worklist<EntryType, SegmentSize>::Local::operator=(
    Worklist<EntryType, SegmentSize>::Local&& other) V8_NOEXCEPT {
  if (this != &other) {
    DCHECK_NULL(worklist_);
    DCHECK_NULL(push_segment_);
    DCHECK_NULL(pop_segment_);
    worklist_ = other.worklist_;
    push_segment_ = other.push_segment_;
    pop_segment_ = other.pop_segment_;
    other.worklist_ = nullptr;
    other.push_segment_ = nullptr;
    other.pop_segment_ = nullptr;
Omer Katz's avatar
Omer Katz committed
386
  }
387 388 389
  return *this;
}

390
template <typename EntryType, uint16_t SegmentSize>
391
void Worklist<EntryType, SegmentSize>::Local::Push(EntryType entry) {
392
  if (V8_UNLIKELY(push_segment_->IsFull())) {
393
    PublishPushSegment();
Omer Katz's avatar
Omer Katz committed
394
  }
395
  push_segment()->Push(entry);
396 397
}

398
template <typename EntryType, uint16_t SegmentSize>
399
bool Worklist<EntryType, SegmentSize>::Local::Pop(EntryType* entry) {
400
  if (pop_segment_->IsEmpty()) {
401 402 403 404
    if (!push_segment_->IsEmpty()) {
      std::swap(push_segment_, pop_segment_);
    } else if (!StealPopSegment()) {
      return false;
Omer Katz's avatar
Omer Katz committed
405 406
    }
  }
407
  pop_segment()->Pop(entry);
408 409 410
  return true;
}

411
template <typename EntryType, uint16_t SegmentSize>
412 413 414 415
bool Worklist<EntryType, SegmentSize>::Local::IsLocalAndGlobalEmpty() const {
  return IsLocalEmpty() && IsGlobalEmpty();
}

416
template <typename EntryType, uint16_t SegmentSize>
417 418 419 420
bool Worklist<EntryType, SegmentSize>::Local::IsLocalEmpty() const {
  return push_segment_->IsEmpty() && pop_segment_->IsEmpty();
}

421
template <typename EntryType, uint16_t SegmentSize>
422 423 424 425
bool Worklist<EntryType, SegmentSize>::Local::IsGlobalEmpty() const {
  return worklist_->IsEmpty();
}

426
template <typename EntryType, uint16_t SegmentSize>
427
void Worklist<EntryType, SegmentSize>::Local::Publish() {
428 429
  if (!push_segment_->IsEmpty()) PublishPushSegment();
  if (!pop_segment_->IsEmpty()) PublishPopSegment();
430 431
}

432
template <typename EntryType, uint16_t SegmentSize>
433 434 435 436 437 438
void Worklist<EntryType, SegmentSize>::Local::Merge(
    Worklist<EntryType, SegmentSize>::Local* other) {
  other->Publish();
  worklist_->Merge(other->worklist_);
}

439
template <typename EntryType, uint16_t SegmentSize>
440
void Worklist<EntryType, SegmentSize>::Local::PublishPushSegment() {
441
  if (push_segment_ != internal::SegmentBase::GetSentinelSegmentAddress())
442
    worklist_->Push(push_segment());
443 444 445
  push_segment_ = NewSegment();
}

446
template <typename EntryType, uint16_t SegmentSize>
447
void Worklist<EntryType, SegmentSize>::Local::PublishPopSegment() {
448
  if (pop_segment_ != internal::SegmentBase::GetSentinelSegmentAddress())
449
    worklist_->Push(pop_segment());
450 451 452
  pop_segment_ = NewSegment();
}

453
template <typename EntryType, uint16_t SegmentSize>
454 455 456 457
bool Worklist<EntryType, SegmentSize>::Local::StealPopSegment() {
  if (worklist_->IsEmpty()) return false;
  Segment* new_segment = nullptr;
  if (worklist_->Pop(&new_segment)) {
458
    DeleteSegment(pop_segment_);
459 460
    pop_segment_ = new_segment;
    return true;
Omer Katz's avatar
Omer Katz committed
461
  }
462 463
  return false;
}
Omer Katz's avatar
Omer Katz committed
464

465 466 467 468 469 470 471 472 473 474 475
template <typename EntryType, uint16_t SegmentSize>
bool Worklist<EntryType, SegmentSize>::Local::IsEmpty() const {
  return push_segment_->IsEmpty() && pop_segment_->IsEmpty();
}

template <typename EntryType, uint16_t SegmentSize>
void Worklist<EntryType, SegmentSize>::Local::Clear() {
  push_segment_->Clear();
  pop_segment_->Clear();
}

476 477
}  // namespace base
}  // namespace heap
Omer Katz's avatar
Omer Katz committed
478

479
#endif  // V8_HEAP_BASE_WORKLIST_H_