// Copyright 2018 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
//
// Copied and adopted from V8.
//
// 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 THIRD_PARTY_BLINK_RENDERER_PLATFORM_HEAP_WORKLIST_H_
#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_HEAP_WORKLIST_H_

#include <cstddef>
#include <utility>

#include "base/atomicops.h"
#include "base/compiler_specific.h"
#include "base/gtest_prod_util.h"
#include "base/logging.h"
#include "base/synchronization/lock.h"
#include "third_party/blink/renderer/platform/wtf/allocator.h"

namespace blink {

// 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, int max_tasks = 1>
class Worklist {
  USING_FAST_MALLOC(Worklist);
  using WorklistType = Worklist<EntryType, segment_size, max_tasks>;

 public:
  class View {
   public:
    View(WorklistType* 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() const { return worklist_->IsLocalEmpty(task_id_); }

    // Returns true if the worklist is empty. Can only be used from the main
    // thread without concurrent access.
    bool IsGlobalEmpty() { return worklist_->IsGlobalEmpty(); }

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

    size_t LocalPushSegmentSize() const {
      return worklist_->LocalPushSegmentSize(task_id_);
    }

   private:
    WorklistType* const worklist_;
    const int task_id_;
  };

  static constexpr size_t kSegmentCapacity = segment_size;

  Worklist() : Worklist(max_tasks) {}

  explicit Worklist(int num_tasks) : num_tasks_(num_tasks) {
    CHECK_LE(num_tasks, max_tasks);
    for (int i = 0; i < num_tasks_; i++) {
      private_push_segment(i) = NewSegment();
      private_pop_segment(i) = NewSegment();
    }
  }

  ~Worklist() {
    CHECK(IsGlobalEmpty());
    for (int i = 0; i < num_tasks_; i++) {
      DCHECK(private_push_segment(i));
      DCHECK(private_pop_segment(i));
      delete private_push_segment(i);
      delete private_pop_segment(i);
    }
  }

  bool Push(int task_id, EntryType entry) {
    DCHECK_LT(task_id, num_tasks_);
    DCHECK(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);
      ANALYZER_ALLOW_UNUSED(success);
      DCHECK(success);
    }
    return true;
  }

  bool Pop(int task_id, EntryType* entry) {
    DCHECK_LT(task_id, num_tasks_);
    DCHECK(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);
      ANALYZER_ALLOW_UNUSED(success);
      DCHECK(success);
    }
    return true;
  }

  bool IsLocalEmpty(int task_id) const {
    return private_pop_segment(task_id)->IsEmpty() &&
           private_push_segment(task_id)->IsEmpty();
  }

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

  bool IsGlobalEmpty() {
    for (int i = 0; i < num_tasks_; i++) {
      if (!IsLocalEmpty(i))
        return false;
    }
    return global_pool_.IsEmpty();
  }

  size_t LocalSize(int task_id) const {
    return private_pop_segment(task_id)->Size() +
           private_push_segment(task_id)->Size();
  }

  size_t LocalPushSegmentSize(int task_id) const {
    return private_push_segment(task_id)->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);
  }

  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) {
    auto pair = other->global_pool_.Extract();
    global_pool_.MergeList(pair.first, pair.second);
  }

 private:
  FRIEND_TEST_ALL_PREFIXES(WorklistTest, SegmentCreate);
  FRIEND_TEST_ALL_PREFIXES(WorklistTest, SegmentPush);
  FRIEND_TEST_ALL_PREFIXES(WorklistTest, SegmentPushPop);
  FRIEND_TEST_ALL_PREFIXES(WorklistTest, SegmentIsEmpty);
  FRIEND_TEST_ALL_PREFIXES(WorklistTest, SegmentIsFull);
  FRIEND_TEST_ALL_PREFIXES(WorklistTest, SegmentClear);
  FRIEND_TEST_ALL_PREFIXES(WorklistTest, SegmentFullPushFails);
  FRIEND_TEST_ALL_PREFIXES(WorklistTest, SegmentEmptyPopFails);
  FRIEND_TEST_ALL_PREFIXES(WorklistTest, SegmentUpdateFalse);
  FRIEND_TEST_ALL_PREFIXES(WorklistTest, SegmentUpdate);

  class Segment {
    USING_FAST_MALLOC(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) {}

    inline void Push(Segment* segment) {
      base::AutoLock guard(lock_);
      segment->set_next(top_);
      set_top(segment);
    }

    inline bool Pop(Segment** segment) {
      base::AutoLock guard(lock_);
      if (top_) {
        *segment = top_;
        set_top(top_->next());
        return true;
      }
      return false;
    }

    inline bool IsEmpty() {
      return base::subtle::NoBarrier_Load(
                 reinterpret_cast<base::subtle::AtomicWord*>(&top_)) == 0;
    }

    void Clear() {
      base::AutoLock guard(lock_);
      Segment* current = top_;
      while (current) {
        Segment* tmp = current;
        current = current->next();
        delete tmp;
      }
      set_top(nullptr);
    }

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

    std::pair<Segment*, Segment*> Extract() {
      Segment* top = nullptr;
      {
        base::AutoLock guard(lock_);
        if (!top_)
          return std::make_pair(nullptr, nullptr);
        top = top_;
        set_top(nullptr);
      }
      Segment* end = top;
      while (end->next())
        end = end->next();
      return std::make_pair(top, end);
    }

    void MergeList(Segment* start, Segment* end) {
      if (!start)
        return;
      {
        base::AutoLock guard(lock_);
        end->set_next(top_);
        set_top(start);
      }
    }

   private:
    void set_top(Segment* segment) {
      return base::subtle::NoBarrier_Store(
          reinterpret_cast<base::subtle::AtomicWord*>(&top_),
          reinterpret_cast<base::subtle::AtomicWord>(segment));
    }

    mutable base::Lock lock_;
    Segment* top_;
  };

  ALWAYS_INLINE Segment*& private_push_segment(int task_id) {
    return private_segments_[task_id].private_push_segment;
  }

  ALWAYS_INLINE Segment* const& private_push_segment(int task_id) const {
    return const_cast<const PrivateSegmentHolder*>(private_segments_)[task_id]
        .private_push_segment;
  }

  ALWAYS_INLINE Segment*& private_pop_segment(int task_id) {
    return private_segments_[task_id].private_pop_segment;
  }

  ALWAYS_INLINE Segment* const& private_pop_segment(int task_id) const {
    return const_cast<const PrivateSegmentHolder*>(private_segments_)[task_id]
        .private_pop_segment;
  }

  ALWAYS_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();
    }
  }

  ALWAYS_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();
    }
  }

  ALWAYS_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;
  }

  ALWAYS_INLINE Segment* NewSegment() {
    // Bottleneck for filtering in crash dumps.
    return new Segment();
  }

  PrivateSegmentHolder private_segments_[max_tasks];
  GlobalPool global_pool_;
  int num_tasks_;
};

}  // namespace blink

#endif  // THIRD_PARTY_BLINK_RENDERER_PLATFORM_HEAP_WORKLIST_H_