blob: 80b4a4f01f2864e3aecb7a02858c463ce86c3932 [file] [log] [blame]
// 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/free-list.h"
#include "src/base/macros.h"
#include "src/common/globals.h"
#include "src/heap/free-list-inl.h"
#include "src/heap/heap.h"
#include "src/heap/memory-chunk-inl.h"
#include "src/objects/free-space-inl.h"
namespace v8 {
namespace internal {
// -----------------------------------------------------------------------------
// Free lists for old object spaces implementation
void FreeListCategory::Reset(FreeList* owner) {
if (is_linked(owner) && !top().is_null()) {
owner->DecreaseAvailableBytes(available_);
}
set_top(FreeSpace());
set_prev(nullptr);
set_next(nullptr);
available_ = 0;
}
FreeSpace FreeListCategory::PickNodeFromList(size_t minimum_size,
size_t* node_size) {
FreeSpace node = top();
DCHECK(!node.is_null());
DCHECK(Page::FromHeapObject(node)->CanAllocate());
if (static_cast<size_t>(node.Size()) < minimum_size) {
*node_size = 0;
return FreeSpace();
}
set_top(node.next());
*node_size = node.Size();
UpdateCountersAfterAllocation(*node_size);
return node;
}
FreeSpace FreeListCategory::SearchForNodeInList(size_t minimum_size,
size_t* node_size) {
FreeSpace prev_non_evac_node;
for (FreeSpace cur_node = top(); !cur_node.is_null();
cur_node = cur_node.next()) {
DCHECK(Page::FromHeapObject(cur_node)->CanAllocate());
size_t size = cur_node.size();
if (size >= minimum_size) {
DCHECK_GE(available_, size);
UpdateCountersAfterAllocation(size);
if (cur_node == top()) {
set_top(cur_node.next());
}
if (!prev_non_evac_node.is_null()) {
MemoryChunk* chunk = MemoryChunk::FromHeapObject(prev_non_evac_node);
if (chunk->owner_identity() == CODE_SPACE) {
chunk->heap()->UnprotectAndRegisterMemoryChunk(chunk);
}
prev_non_evac_node.set_next(cur_node.next());
}
*node_size = size;
return cur_node;
}
prev_non_evac_node = cur_node;
}
return FreeSpace();
}
void FreeListCategory::Free(Address start, size_t size_in_bytes, FreeMode mode,
FreeList* owner) {
FreeSpace free_space = FreeSpace::cast(HeapObject::FromAddress(start));
free_space.set_next(top());
set_top(free_space);
available_ += size_in_bytes;
if (mode == kLinkCategory) {
if (is_linked(owner)) {
owner->IncreaseAvailableBytes(size_in_bytes);
} else {
owner->AddCategory(this);
}
}
}
void FreeListCategory::RepairFreeList(Heap* heap) {
Map free_space_map = ReadOnlyRoots(heap).free_space_map();
FreeSpace n = top();
while (!n.is_null()) {
ObjectSlot map_slot = n.map_slot();
if (map_slot.contains_value(kNullAddress)) {
map_slot.store(free_space_map);
} else {
DCHECK(map_slot.contains_value(free_space_map.ptr()));
}
n = n.next();
}
}
void FreeListCategory::Relink(FreeList* owner) {
DCHECK(!is_linked(owner));
owner->AddCategory(this);
}
// ------------------------------------------------
// Generic FreeList methods (alloc/free related)
FreeList* FreeList::CreateFreeList() { return new FreeListManyCachedOrigin(); }
FreeSpace FreeList::TryFindNodeIn(FreeListCategoryType type,
size_t minimum_size, size_t* node_size) {
FreeListCategory* category = categories_[type];
if (category == nullptr) return FreeSpace();
FreeSpace node = category->PickNodeFromList(minimum_size, node_size);
if (!node.is_null()) {
DecreaseAvailableBytes(*node_size);
DCHECK(IsVeryLong() || Available() == SumFreeLists());
}
if (category->is_empty()) {
RemoveCategory(category);
}
return node;
}
FreeSpace FreeList::SearchForNodeInList(FreeListCategoryType type,
size_t minimum_size,
size_t* node_size) {
FreeListCategoryIterator it(this, type);
FreeSpace node;
while (it.HasNext()) {
FreeListCategory* current = it.Next();
node = current->SearchForNodeInList(minimum_size, node_size);
if (!node.is_null()) {
DecreaseAvailableBytes(*node_size);
DCHECK(IsVeryLong() || Available() == SumFreeLists());
if (current->is_empty()) {
RemoveCategory(current);
}
return node;
}
}
return node;
}
size_t FreeList::Free(Address start, size_t size_in_bytes, FreeMode mode) {
Page* page = Page::FromAddress(start);
page->DecreaseAllocatedBytes(size_in_bytes);
// Blocks have to be a minimum size to hold free list items.
if (size_in_bytes < min_block_size_) {
page->add_wasted_memory(size_in_bytes);
wasted_bytes_ += size_in_bytes;
return size_in_bytes;
}
// Insert other blocks at the head of a free list of the appropriate
// magnitude.
FreeListCategoryType type = SelectFreeListCategoryType(size_in_bytes);
page->free_list_category(type)->Free(start, size_in_bytes, mode, this);
DCHECK_EQ(page->AvailableInFreeList(),
page->AvailableInFreeListFromAllocatedBytes());
return 0;
}
// ------------------------------------------------
// FreeListMany implementation
constexpr unsigned int FreeListMany::categories_min[kNumberOfCategories];
FreeListMany::FreeListMany() {
// Initializing base (FreeList) fields
number_of_categories_ = kNumberOfCategories;
last_category_ = number_of_categories_ - 1;
min_block_size_ = kMinBlockSize;
categories_ = new FreeListCategory*[number_of_categories_]();
Reset();
}
FreeListMany::~FreeListMany() { delete[] categories_; }
size_t FreeListMany::GuaranteedAllocatable(size_t maximum_freed) {
if (maximum_freed < categories_min[0]) {
return 0;
}
for (int cat = kFirstCategory + 1; cat <= last_category_; cat++) {
if (maximum_freed < categories_min[cat]) {
return categories_min[cat - 1];
}
}
return maximum_freed;
}
Page* FreeListMany::GetPageForSize(size_t size_in_bytes) {
FreeListCategoryType minimum_category =
SelectFreeListCategoryType(size_in_bytes);
Page* page = nullptr;
for (int cat = minimum_category + 1; !page && cat <= last_category_; cat++) {
page = GetPageForCategoryType(cat);
}
if (!page) {
// Might return a page in which |size_in_bytes| will not fit.
page = GetPageForCategoryType(minimum_category);
}
return page;
}
FreeSpace FreeListMany::Allocate(size_t size_in_bytes, size_t* node_size,
AllocationOrigin origin) {
DCHECK_GE(kMaxBlockSize, size_in_bytes);
FreeSpace node;
FreeListCategoryType type = SelectFreeListCategoryType(size_in_bytes);
for (int i = type; i < last_category_ && node.is_null(); i++) {
node = TryFindNodeIn(static_cast<FreeListCategoryType>(i), size_in_bytes,
node_size);
}
if (node.is_null()) {
// Searching each element of the last category.
node = SearchForNodeInList(last_category_, size_in_bytes, node_size);
}
if (!node.is_null()) {
Page::FromHeapObject(node)->IncreaseAllocatedBytes(*node_size);
}
DCHECK(IsVeryLong() || Available() == SumFreeLists());
return node;
}
// ------------------------------------------------
// FreeListManyCached implementation
FreeListManyCached::FreeListManyCached() { ResetCache(); }
void FreeListManyCached::Reset() {
ResetCache();
FreeListMany::Reset();
}
bool FreeListManyCached::AddCategory(FreeListCategory* category) {
bool was_added = FreeList::AddCategory(category);
// Updating cache
if (was_added) {
UpdateCacheAfterAddition(category->type_);
}
#ifdef DEBUG
CheckCacheIntegrity();
#endif
return was_added;
}
void FreeListManyCached::RemoveCategory(FreeListCategory* category) {
FreeList::RemoveCategory(category);
// Updating cache
int type = category->type_;
if (categories_[type] == nullptr) {
UpdateCacheAfterRemoval(type);
}
#ifdef DEBUG
CheckCacheIntegrity();
#endif
}
size_t FreeListManyCached::Free(Address start, size_t size_in_bytes,
FreeMode mode) {
Page* page = Page::FromAddress(start);
page->DecreaseAllocatedBytes(size_in_bytes);
// Blocks have to be a minimum size to hold free list items.
if (size_in_bytes < min_block_size_) {
page->add_wasted_memory(size_in_bytes);
wasted_bytes_ += size_in_bytes;
return size_in_bytes;
}
// Insert other blocks at the head of a free list of the appropriate
// magnitude.
FreeListCategoryType type = SelectFreeListCategoryType(size_in_bytes);
page->free_list_category(type)->Free(start, size_in_bytes, mode, this);
// Updating cache
if (mode == kLinkCategory) {
UpdateCacheAfterAddition(type);
#ifdef DEBUG
CheckCacheIntegrity();
#endif
}
DCHECK_EQ(page->AvailableInFreeList(),
page->AvailableInFreeListFromAllocatedBytes());
return 0;
}
FreeSpace FreeListManyCached::Allocate(size_t size_in_bytes, size_t* node_size,
AllocationOrigin origin) {
USE(origin);
DCHECK_GE(kMaxBlockSize, size_in_bytes);
FreeSpace node;
FreeListCategoryType type = SelectFreeListCategoryType(size_in_bytes);
type = next_nonempty_category[type];
for (; type < last_category_; type = next_nonempty_category[type + 1]) {
node = TryFindNodeIn(type, size_in_bytes, node_size);
if (!node.is_null()) break;
}
if (node.is_null()) {
// Searching each element of the last category.
type = last_category_;
node = SearchForNodeInList(type, size_in_bytes, node_size);
}
// Updating cache
if (!node.is_null() && categories_[type] == nullptr) {
UpdateCacheAfterRemoval(type);
}
#ifdef DEBUG
CheckCacheIntegrity();
#endif
if (!node.is_null()) {
Page::FromHeapObject(node)->IncreaseAllocatedBytes(*node_size);
}
DCHECK(IsVeryLong() || Available() == SumFreeLists());
return node;
}
// ------------------------------------------------
// FreeListManyCachedFastPath implementation
FreeSpace FreeListManyCachedFastPath::Allocate(size_t size_in_bytes,
size_t* node_size,
AllocationOrigin origin) {
USE(origin);
DCHECK_GE(kMaxBlockSize, size_in_bytes);
FreeSpace node;
// Fast path part 1: searching the last categories
FreeListCategoryType first_category =
SelectFastAllocationFreeListCategoryType(size_in_bytes);
FreeListCategoryType type = first_category;
for (type = next_nonempty_category[type]; type <= last_category_;
type = next_nonempty_category[type + 1]) {
node = TryFindNodeIn(type, size_in_bytes, node_size);
if (!node.is_null()) break;
}
// Fast path part 2: searching the medium categories for tiny objects
if (node.is_null()) {
if (size_in_bytes <= kTinyObjectMaxSize) {
for (type = next_nonempty_category[kFastPathFallBackTiny];
type < kFastPathFirstCategory;
type = next_nonempty_category[type + 1]) {
node = TryFindNodeIn(type, size_in_bytes, node_size);
if (!node.is_null()) break;
}
}
}
// Searching the last category
if (node.is_null()) {
// Searching each element of the last category.
type = last_category_;
node = SearchForNodeInList(type, size_in_bytes, node_size);
}
// Finally, search the most precise category
if (node.is_null()) {
type = SelectFreeListCategoryType(size_in_bytes);
for (type = next_nonempty_category[type]; type < first_category;
type = next_nonempty_category[type + 1]) {
node = TryFindNodeIn(type, size_in_bytes, node_size);
if (!node.is_null()) break;
}
}
// Updating cache
if (!node.is_null() && categories_[type] == nullptr) {
UpdateCacheAfterRemoval(type);
}
#ifdef DEBUG
CheckCacheIntegrity();
#endif
if (!node.is_null()) {
Page::FromHeapObject(node)->IncreaseAllocatedBytes(*node_size);
}
DCHECK(IsVeryLong() || Available() == SumFreeLists());
return node;
}
// ------------------------------------------------
// FreeListManyCachedOrigin implementation
FreeSpace FreeListManyCachedOrigin::Allocate(size_t size_in_bytes,
size_t* node_size,
AllocationOrigin origin) {
if (origin == AllocationOrigin::kGC) {
return FreeListManyCached::Allocate(size_in_bytes, node_size, origin);
} else {
return FreeListManyCachedFastPath::Allocate(size_in_bytes, node_size,
origin);
}
}
// ------------------------------------------------
// Generic FreeList methods (non alloc/free related)
void FreeList::Reset() {
ForAllFreeListCategories(
[this](FreeListCategory* category) { category->Reset(this); });
for (int i = kFirstCategory; i < number_of_categories_; i++) {
categories_[i] = nullptr;
}
wasted_bytes_ = 0;
available_ = 0;
}
size_t FreeList::EvictFreeListItems(Page* page) {
size_t sum = 0;
page->ForAllFreeListCategories([this, &sum](FreeListCategory* category) {
sum += category->available();
RemoveCategory(category);
category->Reset(this);
});
return sum;
}
void FreeList::RepairLists(Heap* heap) {
ForAllFreeListCategories(
[heap](FreeListCategory* category) { category->RepairFreeList(heap); });
}
bool FreeList::AddCategory(FreeListCategory* category) {
FreeListCategoryType type = category->type_;
DCHECK_LT(type, number_of_categories_);
FreeListCategory* top = categories_[type];
if (category->is_empty()) return false;
DCHECK_NE(top, category);
// Common double-linked list insertion.
if (top != nullptr) {
top->set_prev(category);
}
category->set_next(top);
categories_[type] = category;
IncreaseAvailableBytes(category->available());
return true;
}
void FreeList::RemoveCategory(FreeListCategory* category) {
FreeListCategoryType type = category->type_;
DCHECK_LT(type, number_of_categories_);
FreeListCategory* top = categories_[type];
if (category->is_linked(this)) {
DecreaseAvailableBytes(category->available());
}
// Common double-linked list removal.
if (top == category) {
categories_[type] = category->next();
}
if (category->prev() != nullptr) {
category->prev()->set_next(category->next());
}
if (category->next() != nullptr) {
category->next()->set_prev(category->prev());
}
category->set_next(nullptr);
category->set_prev(nullptr);
}
void FreeList::PrintCategories(FreeListCategoryType type) {
FreeListCategoryIterator it(this, type);
PrintF("FreeList[%p, top=%p, %d] ", static_cast<void*>(this),
static_cast<void*>(categories_[type]), type);
while (it.HasNext()) {
FreeListCategory* current = it.Next();
PrintF("%p -> ", static_cast<void*>(current));
}
PrintF("null\n");
}
size_t FreeListCategory::SumFreeList() {
size_t sum = 0;
FreeSpace cur = top();
while (!cur.is_null()) {
// We can't use "cur->map()" here because both cur's map and the
// root can be null during bootstrapping.
DCHECK(cur.map_slot().contains_value(Page::FromHeapObject(cur)
->heap()
->isolate()
->root(RootIndex::kFreeSpaceMap)
.ptr()));
sum += cur.relaxed_read_size();
cur = cur.next();
}
return sum;
}
int FreeListCategory::FreeListLength() {
int length = 0;
FreeSpace cur = top();
while (!cur.is_null()) {
length++;
cur = cur.next();
}
return length;
}
#ifdef DEBUG
bool FreeList::IsVeryLong() {
int len = 0;
for (int i = kFirstCategory; i < number_of_categories_; i++) {
FreeListCategoryIterator it(this, static_cast<FreeListCategoryType>(i));
while (it.HasNext()) {
len += it.Next()->FreeListLength();
if (len >= FreeListCategory::kVeryLongFreeList) return true;
}
}
return false;
}
// This can take a very long time because it is linear in the number of entries
// on the free list, so it should not be called if FreeListLength returns
// kVeryLongFreeList.
size_t FreeList::SumFreeLists() {
size_t sum = 0;
ForAllFreeListCategories(
[&sum](FreeListCategory* category) { sum += category->SumFreeList(); });
return sum;
}
#endif
} // namespace internal
} // namespace v8