[heap] Move to two-level free-list

src/heap/spaces-inl.h

 // Copyright 2011 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 V8_HEAP_SPACES_INL_H_
 #define V8_HEAP_SPACES_INL_H_
 
 #include "src/heap/incremental-marking.h"
 #include "src/heap/spaces.h"
 #include "src/isolate.h"
@@ skipping 244 matching lines @@
 // --------------------------------------------------------------------------
 // PagedSpace
 
 Page* Page::Initialize(Heap* heap, MemoryChunk* chunk, Executability executable,
                        PagedSpace* owner) {
   Page* page = reinterpret_cast<Page*>(chunk);
   page->mutex_ = new base::Mutex();
   DCHECK(page->area_size() <= kAllocatableMemory);
   DCHECK(chunk->owner() == owner);
   owner->IncreaseCapacity(page->area_size());
+  heap->incremental_marking()->SetOldSpacePageFlags(chunk);
+
+  // Make sure that categories are initialized before freeing the area.
+  page->InitializeFreeListCategories();
   owner->Free(page->area_start(), page->area_size());
 
-  heap->incremental_marking()->SetOldSpacePageFlags(chunk);
+  return page;
+}
 
-  return page;
+void Page::InitializeFreeListCategories() {
+  for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
+    categories_[i].Initialize(static_cast<FreeListCategoryType>(i));
+  }
 }
 
 void MemoryChunk::IncrementLiveBytesFromGC(HeapObject* object, int by) {
   MemoryChunk::FromAddress(object->address())->IncrementLiveBytes(by);
 }
 
 void MemoryChunk::ResetLiveBytes() {
   if (FLAG_trace_live_bytes) {
     PrintIsolate(heap()->isolate(), "live-bytes: reset page=%p %d->0\n", this,
                  live_byte_count_);
@@ skipping 27 matching lines @@
   return p->owner() == this;
 }
 
 bool PagedSpace::Contains(Object* o) {
   if (!o->IsHeapObject()) return false;
   Page* p = Page::FromAddress(HeapObject::cast(o)->address());
   if (!p->is_valid()) return false;
   return p->owner() == this;
 }
 
+void PagedSpace::UnlinkFreeListCategories(Page* page) {
+  DCHECK_EQ(this, page->owner());
+  page->ForAllFreeListCategories([this](FreeListCategory* category) {
+    DCHECK_EQ(free_list(), category->owner());
+    free_list()->RemoveCategory(category);
+  });
+}
+
+intptr_t PagedSpace::RelinkFreeListCategories(Page* page) {
+  DCHECK_EQ(this, page->owner());
+  intptr_t added = 0;
+  page->ForAllFreeListCategories([&added](FreeListCategory* category) {
+    added += category->available();
+    category->Relink();
+  });
+  return added;
+}
+
 MemoryChunk* MemoryChunk::FromAnyPointerAddress(Heap* heap, Address addr) {
   MemoryChunk* chunk = MemoryChunk::FromAddress(addr);
   uintptr_t offset = addr - chunk->address();
   if (offset < MemoryChunk::kHeaderSize || !chunk->HasPageHeader()) {
     chunk = heap->lo_space()->FindPage(addr);
   }
   return chunk;
 }
 
 Page* Page::FromAnyPointerAddress(Heap* heap, Address addr) {
   return static_cast<Page*>(MemoryChunk::FromAnyPointerAddress(heap, addr));
 }
 
+void Page::MarkNeverAllocateForTesting() {
+  DCHECK(!IsFlagSet(NEVER_ALLOCATE_ON_PAGE));
+  SetFlag(NEVER_ALLOCATE_ON_PAGE);
+  reinterpret_cast<PagedSpace*>(owner())->free_list()->EvictFreeListItems(this);
+}
+
+void Page::MarkEvacuationCandidate() {
+  DCHECK(!IsFlagSet(NEVER_EVACUATE));
+  DCHECK_NULL(old_to_old_slots_);
+  DCHECK_NULL(typed_old_to_old_slots_);
+  SetFlag(EVACUATION_CANDIDATE);
+  reinterpret_cast<PagedSpace*>(owner())->free_list()->EvictFreeListItems(this);
+}
+
+void Page::ClearEvacuationCandidate() {
+  DCHECK_NULL(old_to_old_slots_);
+  DCHECK_NULL(typed_old_to_old_slots_);
+  ClearFlag(EVACUATION_CANDIDATE);
+  InitializeFreeListCategories();
+}
+
 MemoryChunkIterator::MemoryChunkIterator(Heap* heap, Mode mode)
     : state_(kOldSpaceState),
       mode_(mode),
       old_iterator_(heap->old_space()),
       code_iterator_(heap->code_space()),
       map_iterator_(heap->map_space()),
       lo_iterator_(heap->lo_space()) {}
 
 MemoryChunk* MemoryChunkIterator::next() {
   switch (state_) {
@@ skipping 28 matching lines @@
     }
     case kFinishedState:
       return nullptr;
     default:
       break;
   }
   UNREACHABLE();
   return nullptr;
 }
 
-
 void Page::set_next_page(Page* page) {
   DCHECK(page->owner() == owner());
   set_next_chunk(page);
 }
 
-
 void Page::set_prev_page(Page* page) {
   DCHECK(page->owner() == owner());
   set_prev_chunk(page);
 }
 
+Page* FreeListCategory::page() {
+  return Page::FromAddress(reinterpret_cast<Address>(this));
+}
+
+FreeList* FreeListCategory::owner() {
+  return reinterpret_cast<PagedSpace*>(
+             Page::FromAddress(reinterpret_cast<Address>(this))->owner())
+      ->free_list();
+}
+
+bool FreeListCategory::is_linked() {
+  return prev_ != nullptr || next_ != nullptr || owner()->top(type_) == this;
+}
 
 // Try linear allocation in the page of alloc_info's allocation top.  Does
 // not contain slow case logic (e.g. move to the next page or try free list
 // allocation) so it can be used by all the allocation functions and for all
 // the paged spaces.
 HeapObject* PagedSpace::AllocateLinearly(int size_in_bytes) {
   Address current_top = allocation_info_.top();
   Address new_top = current_top + size_in_bytes;
   if (new_top > allocation_info_.limit()) return NULL;
 
@@ skipping 231 matching lines @@
     other->allocation_info_.Reset(nullptr, nullptr);
     return true;
   }
   return false;
 }
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_HEAP_SPACES_INL_H_