diff options
Diffstat (limited to 'deps/v8/src/heap/cppgc/free-list.cc')
-rw-r--r-- | deps/v8/src/heap/cppgc/free-list.cc | 190 |
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 |