[heap] Refactor free list counters in Page.

src/heap/spaces.cc

 // 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.
 
 #include "src/heap/spaces.h"
 
 #include "src/base/bits.h"
 #include "src/base/platform/platform.h"
 #include "src/full-codegen/full-codegen.h"
 #include "src/heap/slot-set.h"
@@ skipping 470 matching lines @@
   chunk->slots_buffer_ = nullptr;
   chunk->old_to_new_slots_ = nullptr;
   chunk->old_to_old_slots_ = nullptr;
   chunk->skip_list_ = nullptr;
   chunk->write_barrier_counter_ = kWriteBarrierCounterGranularity;
   chunk->progress_bar_ = 0;
   chunk->high_water_mark_.SetValue(static_cast<intptr_t>(area_start - base));
   chunk->concurrent_sweeping_state().SetValue(kSweepingDone);
   chunk->parallel_compaction_state().SetValue(kCompactingDone);
   chunk->mutex_ = nullptr;
-  chunk->available_in_small_free_list_ = 0;
-  chunk->available_in_medium_free_list_ = 0;
-  chunk->available_in_large_free_list_ = 0;
-  chunk->available_in_huge_free_list_ = 0;
-  chunk->non_available_small_blocks_ = 0;
+  chunk->available_in_free_list_ = 0;
+  chunk->wasted_memory_ = 0;
   chunk->ResetLiveBytes();
   Bitmap::Clear(chunk);
   chunk->set_next_chunk(nullptr);
   chunk->set_prev_chunk(nullptr);
 
   DCHECK(OFFSET_OF(MemoryChunk, flags_) == kFlagsOffset);
   DCHECK(OFFSET_OF(MemoryChunk, live_byte_count_) == kLiveBytesOffset);
 
   if (executable == EXECUTABLE) {
     chunk->SetFlag(IS_EXECUTABLE);
@@ skipping 203 matching lines @@
     ObjectSpace space = static_cast<ObjectSpace>(1 << owner->identity());
     PerformAllocationCallback(space, kAllocationActionAllocate, chunk_size);
   }
 
   return MemoryChunk::Initialize(heap, base, chunk_size, area_start, area_end,
                                  executable, owner, &reservation);
 }
 
 
 void Page::ResetFreeListStatistics() {
-  non_available_small_blocks_ = 0;
-  available_in_small_free_list_ = 0;
-  available_in_medium_free_list_ = 0;
-  available_in_large_free_list_ = 0;
-  available_in_huge_free_list_ = 0;
+  wasted_memory_ = 0;
+  available_in_free_list_ = 0;
 }
 
 
 Page* MemoryAllocator::AllocatePage(intptr_t size, PagedSpace* owner,
                                     Executability executable) {
   MemoryChunk* chunk = AllocateChunk(size, size, executable, owner);
   if (chunk == NULL) return NULL;
   return Page::Initialize(isolate_->heap(), chunk, executable, owner);
 }
 
@@ skipping 1467 matching lines @@
       if (cur_node == end()) {
         set_end(prev_node);
       }
       if (prev_node != nullptr) {
         prev_node->set_next(cur_node->next());
       }
       continue;
     }
     prev_node = cur_node;
   }
-  DCHECK_EQ(p->available_in_free_list(type_), sum);
-  p->add_available_in_free_list(type_, -sum);
+  p->add_available_in_free_list(-sum);
   available_ -= sum;
   return sum;
 }
 
 
 bool FreeListCategory::ContainsPageFreeListItemsInList(Page* p) {
   FreeSpace* node = top();
   while (node != NULL) {
     if (Page::FromAddress(node->address()) == p) return true;
     node = node->next();
   }
   return false;
 }
 
 
 FreeSpace* FreeListCategory::PickNodeFromList(int* node_size) {
   FreeSpace* node = top();
   if (node == nullptr) return nullptr;
 
   Page* page = Page::FromAddress(node->address());
   while ((node != nullptr) && !page->CanAllocate()) {
     available_ -= node->size();
-    page->add_available_in_free_list(type_, -(node->Size()));
+    page->add_available_in_free_list(-(node->Size()));
     node = node->next();
   }
 
   if (node != nullptr) {
     set_top(node->next());
     *node_size = node->Size();
     available_ -= *node_size;
   } else {
     set_top(nullptr);
   }
@@ skipping 34 matching lines @@
         set_top(cur_node->next());
       }
       if (cur_node == end()) {
         set_end(prev_non_evac_node);
       }
       if (prev_non_evac_node != nullptr) {
         prev_non_evac_node->set_next(cur_node->next());
       }
       // For evacuation candidates we continue.
       if (!page_for_node->CanAllocate()) {
-        page_for_node->add_available_in_free_list(type_, -size);
+        page_for_node->add_available_in_free_list(-size);
         continue;
       }
       // Otherwise we have a large enough node and can return.
       *node_size = size;
       return cur_node;
     }
 
     prev_non_evac_node = cur_node;
   }
   return nullptr;
@@ skipping 67 matching lines @@
 
 int FreeList::Free(Address start, int size_in_bytes) {
   if (size_in_bytes == 0) return 0;
 
   owner()->heap()->CreateFillerObjectAt(start, size_in_bytes);
 
   Page* page = Page::FromAddress(start);
 
   // Early return to drop too-small blocks on the floor.
   if (size_in_bytes <= kSmallListMin) {
-    page->add_non_available_small_blocks(size_in_bytes);
+    page->add_wasted_memory(size_in_bytes);
     wasted_bytes_ += size_in_bytes;
     return size_in_bytes;
   }
 
   FreeSpace* free_space = FreeSpace::cast(HeapObject::FromAddress(start));
   // Insert other blocks at the head of a free list of the appropriate
   // magnitude.
-  if (size_in_bytes <= kSmallListMax) {
-    category_[kSmall].Free(free_space, size_in_bytes);
-    page->add_available_in_small_free_list(size_in_bytes);
-  } else if (size_in_bytes <= kMediumListMax) {
-    category_[kMedium].Free(free_space, size_in_bytes);
-    page->add_available_in_medium_free_list(size_in_bytes);
-  } else if (size_in_bytes <= kLargeListMax) {
-    category_[kLarge].Free(free_space, size_in_bytes);
-    page->add_available_in_large_free_list(size_in_bytes);
-  } else {
-    category_[kHuge].Free(free_space, size_in_bytes);
-    page->add_available_in_huge_free_list(size_in_bytes);
-  }
+  FreeListCategoryType type = SelectFreeListCategoryType(size_in_bytes);
+  category_[type].Free(free_space, size_in_bytes);
+  page->add_available_in_free_list(size_in_bytes);
 
   DCHECK(IsVeryLong() || Available() == SumFreeLists());
   return 0;
 }
 
 
 FreeSpace* FreeList::FindNodeIn(FreeListCategoryType category, int* node_size) {
   FreeSpace* node = GetFreeListCategory(category)->PickNodeFromList(node_size);
   if (node != nullptr) {
     Page::FromAddress(node->address())
-        ->add_available_in_free_list(category, -(*node_size));
+        ->add_available_in_free_list(-(*node_size));
     DCHECK(IsVeryLong() || Available() == SumFreeLists());
   }
   return node;
 }
 
 
 FreeSpace* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
   FreeSpace* node = nullptr;
   Page* page = nullptr;
 
-  if (size_in_bytes <= kSmallAllocationMax) {
-    node = FindNodeIn(kSmall, node_size);
+  // First try the allocation fast path: try to allocate the minimum element
+  // size of a free list category. This operation is constant time.
+  FreeListCategoryType type =
+      SelectFastAllocationFreeListCategoryType(size_in_bytes);
+  for (int i = type; i < kHuge; i++) {
+    node = FindNodeIn(static_cast<FreeListCategoryType>(i), node_size);
     if (node != nullptr) return node;
   }
 
-  if (size_in_bytes <= kMediumAllocationMax) {
-    node = FindNodeIn(kMedium, node_size);
-    if (node != nullptr) return node;
-  }
-
-  if (size_in_bytes <= kLargeAllocationMax) {
-    node = FindNodeIn(kLarge, node_size);
-    if (node != nullptr) return node;
-  }
-
+  // Next search the huge list for free list nodes. This takes linear time in
+  // the number of huge elements.
   node = category_[kHuge].SearchForNodeInList(size_in_bytes, node_size);
   if (node != nullptr) {
     page = Page::FromAddress(node->address());
-    page->add_available_in_large_free_list(-(*node_size));
+    page->add_available_in_free_list(-(*node_size));
     DCHECK(IsVeryLong() || Available() == SumFreeLists());
     return node;
   }
 
-  if (size_in_bytes <= kSmallListMax) {
-    node = category_[kSmall].PickNodeFromList(size_in_bytes, node_size);
-    if (node != NULL) {
-      DCHECK(size_in_bytes <= *node_size);
-      page = Page::FromAddress(node->address());
-      page->add_available_in_small_free_list(-(*node_size));
-    }
-  } else if (size_in_bytes <= kMediumListMax) {
-    node = category_[kMedium].PickNodeFromList(size_in_bytes, node_size);
-    if (node != NULL) {
-      DCHECK(size_in_bytes <= *node_size);
-      page = Page::FromAddress(node->address());
-      page->add_available_in_medium_free_list(-(*node_size));
-    }
-  } else if (size_in_bytes <= kLargeListMax) {
-    node = category_[kLarge].PickNodeFromList(size_in_bytes, node_size);
-    if (node != NULL) {
-      DCHECK(size_in_bytes <= *node_size);
-      page = Page::FromAddress(node->address());
-      page->add_available_in_large_free_list(-(*node_size));
-    }
+  // We need a huge block of memory, but we didn't find anything in the huge
+  // list.
+  if (type == kHuge) return nullptr;
+
+  // Now search the best fitting free list for a node that has at least the
+  // requested size. This takes linear time in the number of elements.
+  type = SelectFreeListCategoryType(size_in_bytes);
+  node = category_[type].PickNodeFromList(size_in_bytes, node_size);
+  if (node != nullptr) {
+    DCHECK(size_in_bytes <= *node_size);
+    page = Page::FromAddress(node->address());
+    page->add_available_in_free_list(-(*node_size));
   }
 
   DCHECK(IsVeryLong() || Available() == SumFreeLists());
   return node;
 }
 
 
 FreeSpace* FreeList::TryRemoveMemory(intptr_t hint_size_in_bytes) {
   hint_size_in_bytes = RoundDown(hint_size_in_bytes, kPointerSize);
   base::LockGuard<base::Mutex> guard(&mutex_);
@@ skipping 206 matching lines @@
 // on the heap.  If there was already a free list then the elements on it
 // were created with the wrong FreeSpaceMap (normally NULL), so we need to
 // fix them.
 void PagedSpace::RepairFreeListsAfterDeserialization() {
   free_list_.RepairLists(heap());
   // Each page may have a small free space that is not tracked by a free list.
   // Update the maps for those free space objects.
   PageIterator iterator(this);
   while (iterator.has_next()) {
     Page* page = iterator.next();
-    int size = static_cast<int>(page->non_available_small_blocks());
+    int size = static_cast<int>(page->wasted_memory());
     if (size == 0) continue;
     Address address = page->OffsetToAddress(Page::kPageSize - size);
     heap()->CreateFillerObjectAt(address, size);
   }
 }
 
 
 void PagedSpace::EvictEvacuationCandidatesFromLinearAllocationArea() {
   if (allocation_info_.top() >= allocation_info_.limit()) return;
 
@@ skipping 559 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 }  // namespace internal
 }  // namespace v8