1 files changed, 190 insertions, 0 deletions
diff --git a/deps/v8/src/heap/cppgc/free-list.cc b/deps/v8/src/heap/cppgc/free-list.cc
new file mode 100644
index 00000000000..e5e6b70793d
--- /dev/null
+++ b/deps/v8/src/heap/cppgc/free-list.cc
@@ -0,0 +1,190 @@
+// 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.
+
+#include "src/heap/cppgc/free-list.h"
+
+#include <algorithm>
+
+#include "include/cppgc/internal/logging.h"
+#include "src/base/bits.h"
+#include "src/heap/cppgc/globals.h"
+#include "src/heap/cppgc/heap-object-header-inl.h"
+#include "src/heap/cppgc/sanitizers.h"
+
+namespace cppgc {
+namespace internal {
+
+namespace {
+uint32_t BucketIndexForSize(uint32_t size) {
+  return v8::base::bits::WhichPowerOfTwo(
+      v8::base::bits::RoundDownToPowerOfTwo32(size));
+}
+}  // namespace
+
+class FreeList::Entry : public HeapObjectHeader {
+ public:
+  explicit Entry(size_t size) : HeapObjectHeader(size, kFreeListGCInfoIndex) {
+    static_assert(sizeof(Entry) == kFreeListEntrySize, "Sizes must match");
+  }
+
+  Entry* Next() const { return next_; }
+  void SetNext(Entry* next) { next_ = next; }
+
+  void Link(Entry** previous_next) {
+    next_ = *previous_next;
+    *previous_next = this;
+  }
+  void Unlink(Entry** previous_next) {
+    *previous_next = next_;
+    next_ = nullptr;
+  }
+
+ private:
+  Entry* next_ = nullptr;
+};
+
+FreeList::FreeList() { Clear(); }
+
+FreeList::FreeList(FreeList&& other) V8_NOEXCEPT
+    : free_list_heads_(std::move(other.free_list_heads_)),
+      free_list_tails_(std::move(other.free_list_tails_)),
+      biggest_free_list_index_(std::move(other.biggest_free_list_index_)) {
+  other.Clear();
+}
+
+FreeList& FreeList::operator=(FreeList&& other) V8_NOEXCEPT {
+  Clear();
+  Append(std::move(other));
+  DCHECK(other.IsEmpty());
+  return *this;
+}
+
+void FreeList::Add(FreeList::Block block) {
+  const size_t size = block.size;
+  DCHECK_GT(kPageSize, size);
+  DCHECK_LE(sizeof(HeapObjectHeader), size);
+
+  if (block.size < sizeof(Entry)) {
+    // Create wasted entry. This can happen when an almost emptied linear
+    // allocation buffer is returned to the freelist.
+    new (block.address) HeapObjectHeader(size, kFreeListGCInfoIndex);
+    return;
+  }
+
+  // Make sure the freelist header is writable.
+  SET_MEMORY_ACCESIBLE(block.address, sizeof(Entry));
+  Entry* entry = new (block.address) Entry(size);
+  const size_t index = BucketIndexForSize(static_cast<uint32_t>(size));
+  entry->Link(&free_list_heads_[index]);
+  biggest_free_list_index_ = std::max(biggest_free_list_index_, index);
+  if (!entry->Next()) {
+    free_list_tails_[index] = entry;
+  }
+}
+
+void FreeList::Append(FreeList&& other) {
+#if DEBUG
+  const size_t expected_size = Size() + other.Size();
+#endif
+  // Newly created entries get added to the head.
+  for (size_t index = 0; index < free_list_tails_.size(); ++index) {
+    Entry* other_tail = other.free_list_tails_[index];
+    Entry*& this_head = this->free_list_heads_[index];
+    if (other_tail) {
+      other_tail->SetNext(this_head);
+      if (!this_head) {
+        this->free_list_tails_[index] = other_tail;
+      }
+      this_head = other.free_list_heads_[index];
+      other.free_list_heads_[index] = nullptr;
+      other.free_list_tails_[index] = nullptr;
+    }
+  }
+
+  biggest_free_list_index_ =
+      std::max(biggest_free_list_index_, other.biggest_free_list_index_);
+  other.biggest_free_list_index_ = 0;
+#if DEBUG
+  DCHECK_EQ(expected_size, Size());
+#endif
+  DCHECK(other.IsEmpty());
+}
+
+FreeList::Block FreeList::Allocate(size_t allocation_size) {
+  // Try reusing a block from the largest bin. The underlying reasoning
+  // being that we want to amortize this slow allocation call by carving
+  // off as a large a free block as possible in one go; a block that will
+  // service this block and let following allocations be serviced quickly
+  // by bump allocation.
+  // bucket_size represents minimal size of entries in a bucket.
+  size_t bucket_size = static_cast<size_t>(1) << biggest_free_list_index_;
+  size_t index = biggest_free_list_index_;
+  for (; index > 0; --index, bucket_size >>= 1) {
+    DCHECK(IsConsistent(index));
+    Entry* entry = free_list_heads_[index];
+    if (allocation_size > bucket_size) {
+      // Final bucket candidate; check initial entry if it is able
+      // to service this allocation. Do not perform a linear scan,
+      // as it is considered too costly.
+      if (!entry || entry->GetSize() < allocation_size) break;
+    }
+    if (entry) {
+      if (!entry->Next()) {
+        DCHECK_EQ(entry, free_list_tails_[index]);
+        free_list_tails_[index] = nullptr;
+      }
+      entry->Unlink(&free_list_heads_[index]);
+      biggest_free_list_index_ = index;
+      return {entry, entry->GetSize()};
+    }
+  }
+  biggest_free_list_index_ = index;
+  return {nullptr, 0u};
+}
+
+void FreeList::Clear() {
+  std::fill(free_list_heads_.begin(), free_list_heads_.end(), nullptr);
+  std::fill(free_list_tails_.begin(), free_list_tails_.end(), nullptr);
+  biggest_free_list_index_ = 0;
+}
+
+size_t FreeList::Size() const {
+  size_t size = 0;
+  for (auto* entry : free_list_heads_) {
+    while (entry) {
+      size += entry->GetSize();
+      entry = entry->Next();
+    }
+  }
+  return size;
+}
+
+bool FreeList::IsEmpty() const {
+  return std::all_of(free_list_heads_.cbegin(), free_list_heads_.cend(),
+                     [](const auto* entry) { return !entry; });
+}
+
+bool FreeList::Contains(Block block) const {
+  for (Entry* list : free_list_heads_) {
+    for (Entry* entry = list; entry; entry = entry->Next()) {
+      if (entry <= block.address &&
+          (reinterpret_cast<Address>(block.address) + block.size <=
+           reinterpret_cast<Address>(entry) + entry->GetSize()))
+        return true;
+    }
+  }
+  return false;
+}
+
+bool FreeList::IsConsistent(size_t index) const {
+  // Check that freelist head and tail pointers are consistent, i.e.
+  // - either both are nulls (no entries in the bucket);
+  // - or both are non-nulls and the tail points to the end.
+  return (!free_list_heads_[index] && !free_list_tails_[index]) ||
+         (free_list_heads_[index] && free_list_tails_[index] &&
+          !free_list_tails_[index]->Next());
+}
+
+}  // namespace internal
+}  // namespace cppgc