[heap] Move to two-level free-list

src/heap/spaces-inl.h

Index: src/heap/spaces-inl.h
diff --git a/src/heap/spaces-inl.h b/src/heap/spaces-inl.h
index ccfb24f6e546d56b08e2dc6994190026a156ee89..3ef25cd62f52583b234f42f5b3f9a3a6e7e77b99 100644
--- a/src/heap/spaces-inl.h
+++ b/src/heap/spaces-inl.h
@@ -257,13 +257,21 @@ Page* Page::Initialize(Heap* heap, MemoryChunk* chunk, Executability executable,
   DCHECK(page->area_size() <= kAllocatableMemory);
   DCHECK(chunk->owner() == owner);
   owner->IncreaseCapacity(page->area_size());
-  owner->Free(page->area_start(), 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());
+
   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);
 }
@@ -308,6 +316,24 @@ bool PagedSpace::Contains(Object* o) {
   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();
@@ -321,6 +347,27 @@ 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),
@@ -369,18 +416,29 @@ MemoryChunk* MemoryChunkIterator::next() {
   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