[heap] Use size_t in free list and evacuation candidate selection.

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 <utility>
 
 #include "src/base/bits.h"
 #include "src/base/platform/platform.h"
@@ skipping 758 matching lines @@
   return MemoryChunk::Initialize(heap, base, chunk_size, area_start, area_end,
                                  executable, owner, &reservation);
 }
 
 
 void Page::ResetFreeListStatistics() {
   wasted_memory_ = 0;
   available_in_free_list_ = 0;
 }
 
+size_t Page::AvailableInFreeList() {
+  size_t sum = 0;
+  ForAllFreeListCategories([this, &sum](FreeListCategory* category) {
+    sum += category->available();
+  });
+  return sum;
+}
+
 size_t Page::ShrinkToHighWaterMark() {
   // Shrink pages to high water mark. The water mark points either to a filler
   // or the area_end.
   HeapObject* filler = HeapObject::FromAddress(HighWaterMark());
   if (filler->address() == area_end()) return 0;
   CHECK(filler->IsFiller());
   if (!filler->IsFreeSpace()) return 0;
 
 #ifdef DEBUG
   // Check the the filler is indeed the last filler on the page.
@@ skipping 449 matching lines @@
   for (auto it = other->begin(); it != other->end();) {
     Page* p = *(it++);
 
     // Relinking requires the category to be unlinked.
     other->UnlinkFreeListCategories(p);
 
     p->Unlink();
     p->set_owner(this);
     p->InsertAfter(anchor_.prev_page());
     RelinkFreeListCategories(p);
+    DCHECK_EQ(p->AvailableInFreeList(), p->available_in_free_list());
   }
 }
 
 
 size_t PagedSpace::CommittedPhysicalMemory() {
   if (!base::VirtualMemory::HasLazyCommits()) return CommittedMemory();
   MemoryChunk::UpdateHighWaterMark(allocation_info_.top());
   size_t size = 0;
   for (Page* page : *this) {
     size += page->CommittedPhysicalMemory();
@@ skipping 124 matching lines @@
 
     // Clear the bits in the unused black area.
     if (current_top != current_limit) {
       page->markbits()->ClearRange(page->AddressToMarkbitIndex(current_top),
                                    page->AddressToMarkbitIndex(current_limit));
       page->IncrementLiveBytes(-static_cast<int>(current_limit - current_top));
     }
   }
 
   SetTopAndLimit(NULL, NULL);
-  Free(current_top, static_cast<int>(current_limit - current_top));
+  DCHECK_GE(current_limit, current_top);
+  Free(current_top, current_limit - current_top);
 }
 
 void PagedSpace::IncreaseCapacity(size_t bytes) {
   accounting_stats_.ExpandSpace(bytes);
 }
 
 void PagedSpace::ReleasePage(Page* page) {
   DCHECK_EQ(page->LiveBytes(), 0);
   DCHECK_EQ(page->owner(), this);
 
@@ skipping 189 matching lines @@
       current_page =
           heap()->memory_allocator()->AllocatePage<MemoryAllocator::kPooled>(
               Page::kAllocatableMemory, this, executable());
       if (current_page == nullptr) return false;
       DCHECK_NOT_NULL(current_page);
       current_page->InsertAfter(anchor());
       current_page->ClearLiveness();
       current_page->SetFlags(anchor()->prev_page()->GetFlags(),
                              Page::kCopyAllFlags);
       heap()->CreateFillerObjectAt(current_page->area_start(),
-                                   current_page->area_size(),
+                                   static_cast<int>(current_page->area_size()),
                                    ClearRecordedSlots::kNo);
     }
   }
   return true;
 }
 
 void LocalAllocationBuffer::Close() {
   if (IsValid()) {
     heap_->CreateFillerObjectAt(
         allocation_info_.top(),
@@ skipping 718 matching lines @@
 // Free lists for old object spaces implementation
 
 
 void FreeListCategory::Reset() {
   set_top(nullptr);
   set_prev(nullptr);
   set_next(nullptr);
   available_ = 0;
 }
 
-FreeSpace* FreeListCategory::PickNodeFromList(int* node_size) {
+FreeSpace* FreeListCategory::PickNodeFromList(size_t* node_size) {
   DCHECK(page()->CanAllocate());
 
   FreeSpace* node = top();
   if (node == nullptr) return nullptr;
   set_top(node->next());
   *node_size = node->Size();
   available_ -= *node_size;
   return node;
 }
 
-FreeSpace* FreeListCategory::TryPickNodeFromList(int minimum_size,
-                                                 int* node_size) {
+FreeSpace* FreeListCategory::TryPickNodeFromList(size_t minimum_size,
+                                                 size_t* node_size) {
   DCHECK(page()->CanAllocate());
 
   FreeSpace* node = PickNodeFromList(node_size);
   if ((node != nullptr) && (*node_size < minimum_size)) {
     Free(node, *node_size, kLinkCategory);
     *node_size = 0;
     return nullptr;
   }
   return node;
 }
 
-FreeSpace* FreeListCategory::SearchForNodeInList(int minimum_size,
-                                                 int* node_size) {
+FreeSpace* FreeListCategory::SearchForNodeInList(size_t minimum_size,
+                                                 size_t* node_size) {
   DCHECK(page()->CanAllocate());
 
   FreeSpace* prev_non_evac_node = nullptr;
   for (FreeSpace* cur_node = top(); cur_node != nullptr;
        cur_node = cur_node->next()) {
-    int size = cur_node->size();
+    size_t size = cur_node->size();
     if (size >= minimum_size) {
+      DCHECK_GE(available_, size);
       available_ -= size;
       if (cur_node == top()) {
         set_top(cur_node->next());
       }
       if (prev_non_evac_node != nullptr) {
         prev_non_evac_node->set_next(cur_node->next());
       }
       *node_size = size;
       return cur_node;
     }
 
     prev_non_evac_node = cur_node;
   }
   return nullptr;
 }
 
-bool FreeListCategory::Free(FreeSpace* free_space, int size_in_bytes,
+bool FreeListCategory::Free(FreeSpace* free_space, size_t size_in_bytes,
                             FreeMode mode) {
   if (!page()->CanAllocate()) return false;
 
   free_space->set_next(top());
   set_top(free_space);
   available_ += size_in_bytes;
   if ((mode == kLinkCategory) && (prev() == nullptr) && (next() == nullptr)) {
     owner()->AddCategory(this);
   }
   return true;
@@ skipping 12 matching lines @@
     n = n->next();
   }
 }
 
 void FreeListCategory::Relink() {
   DCHECK(!is_linked());
   owner()->AddCategory(this);
 }
 
 void FreeListCategory::Invalidate() {
-  page()->add_available_in_free_list(-available());
+  page()->remove_available_in_free_list(available());
   Reset();
   type_ = kInvalidCategory;
 }
 
 FreeList::FreeList(PagedSpace* owner) : owner_(owner), wasted_bytes_(0) {
   for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
     categories_[i] = nullptr;
   }
   Reset();
 }
 
 
 void FreeList::Reset() {
   ForAllFreeListCategories(
       [](FreeListCategory* category) { category->Reset(); });
   for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
     categories_[i] = nullptr;
   }
   ResetStats();
 }
 
-int FreeList::Free(Address start, int size_in_bytes, FreeMode mode) {
+size_t FreeList::Free(Address start, size_t size_in_bytes, FreeMode mode) {
   if (size_in_bytes == 0) return 0;
 
-  owner()->heap()->CreateFillerObjectAt(start, size_in_bytes,
+  owner()->heap()->CreateFillerObjectAt(start, static_cast<int>(size_in_bytes),
                                         ClearRecordedSlots::kNo);
 
   Page* page = Page::FromAddress(start);
 
   // Blocks have to be a minimum size to hold free list items.
   if (size_in_bytes < kMinBlockSize) {
     page->add_wasted_memory(size_in_bytes);
     wasted_bytes_.Increment(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.
   FreeListCategoryType type = SelectFreeListCategoryType(size_in_bytes);
   if (page->free_list_category(type)->Free(free_space, size_in_bytes, mode)) {
     page->add_available_in_free_list(size_in_bytes);
   }
+  DCHECK_EQ(page->AvailableInFreeList(), page->available_in_free_list());
   return 0;
 }
 
-FreeSpace* FreeList::FindNodeIn(FreeListCategoryType type, int* node_size) {
+FreeSpace* FreeList::FindNodeIn(FreeListCategoryType type, size_t* node_size) {
   FreeListCategoryIterator it(this, type);
   FreeSpace* node = nullptr;
   while (it.HasNext()) {
     FreeListCategory* current = it.Next();
     node = current->PickNodeFromList(node_size);
     if (node != nullptr) {
       Page::FromAddress(node->address())
-          ->add_available_in_free_list(-(*node_size));
+          ->remove_available_in_free_list(*node_size);
       DCHECK(IsVeryLong() || Available() == SumFreeLists());
       return node;
     }
     RemoveCategory(current);
   }
   return node;
 }
 
-FreeSpace* FreeList::TryFindNodeIn(FreeListCategoryType type, int* node_size,
-                                   int minimum_size) {
+FreeSpace* FreeList::TryFindNodeIn(FreeListCategoryType type, size_t* node_size,
+                                   size_t minimum_size) {
   if (categories_[type] == nullptr) return nullptr;
   FreeSpace* node =
       categories_[type]->TryPickNodeFromList(minimum_size, node_size);
   if (node != nullptr) {
     Page::FromAddress(node->address())
-        ->add_available_in_free_list(-(*node_size));
+        ->remove_available_in_free_list(*node_size);
     DCHECK(IsVeryLong() || Available() == SumFreeLists());
   }
   return node;
 }
 
 FreeSpace* FreeList::SearchForNodeInList(FreeListCategoryType type,
-                                         int* node_size, int minimum_size) {
+                                         size_t* node_size,
+                                         size_t minimum_size) {
   FreeListCategoryIterator it(this, type);
   FreeSpace* node = nullptr;
   while (it.HasNext()) {
     FreeListCategory* current = it.Next();
     node = current->SearchForNodeInList(minimum_size, node_size);
     if (node != nullptr) {
       Page::FromAddress(node->address())
-          ->add_available_in_free_list(-(*node_size));
+          ->remove_available_in_free_list(*node_size);
       DCHECK(IsVeryLong() || Available() == SumFreeLists());
       return node;
     }
     if (current->is_empty()) {
       RemoveCategory(current);
     }
   }
   return node;
 }
 
-FreeSpace* FreeList::FindNodeFor(int size_in_bytes, int* node_size) {
+FreeSpace* FreeList::FindNodeFor(size_t size_in_bytes, size_t* node_size) {
   FreeSpace* node = nullptr;
 
   // 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;
   }
@@ skipping 16 matching lines @@
   node = TryFindNodeIn(type, node_size, size_in_bytes);
 
   DCHECK(IsVeryLong() || Available() == SumFreeLists());
   return node;
 }
 
 // Allocation on the old space free list.  If it succeeds then a new linear
 // allocation space has been set up with the top and limit of the space.  If
 // the allocation fails then NULL is returned, and the caller can perform a GC
 // or allocate a new page before retrying.
-HeapObject* FreeList::Allocate(int size_in_bytes) {
-  DCHECK(0 < size_in_bytes);
+HeapObject* FreeList::Allocate(size_t size_in_bytes) {
   DCHECK(size_in_bytes <= kMaxBlockSize);
   DCHECK(IsAligned(size_in_bytes, kPointerSize));
   // Don't free list allocate if there is linear space available.
-  DCHECK(owner_->limit() - owner_->top() < size_in_bytes);
+  DCHECK_LT(static_cast<size_t>(owner_->limit() - owner_->top()),
+            size_in_bytes);
 
   // Mark the old linear allocation area with a free space map so it can be
   // skipped when scanning the heap.  This also puts it back in the free list
   // if it is big enough.
   owner_->EmptyAllocationInfo();
 
   owner_->heap()->StartIncrementalMarkingIfAllocationLimitIsReached(
       Heap::kNoGCFlags, kNoGCCallbackFlags);
 
-  int new_node_size = 0;
+  size_t new_node_size = 0;
   FreeSpace* new_node = FindNodeFor(size_in_bytes, &new_node_size);
   if (new_node == nullptr) return nullptr;
 
-  int bytes_left = new_node_size - size_in_bytes;
-  DCHECK(bytes_left >= 0);
+  DCHECK_GE(new_node_size, size_in_bytes);
+  size_t bytes_left = new_node_size - size_in_bytes;
 
 #ifdef DEBUG
-  for (int i = 0; i < size_in_bytes / kPointerSize; i++) {
+  for (size_t i = 0; i < size_in_bytes / kPointerSize; i++) {
     reinterpret_cast<Object**>(new_node->address())[i] =
         Smi::FromInt(kCodeZapValue);
   }
 #endif
 
   // The old-space-step might have finished sweeping and restarted marking.
   // Verify that it did not turn the page of the new node into an evacuation
   // candidate.
   DCHECK(!MarkCompactCollector::IsOnEvacuationCandidate(new_node));
 
-  const int kThreshold = IncrementalMarking::kAllocatedThreshold;
+  const size_t kThreshold = IncrementalMarking::kAllocatedThreshold;
 
   // Memory in the linear allocation area is counted as allocated.  We may free
   // a little of this again immediately - see below.
-  owner_->Allocate(new_node_size);
+  owner_->Allocate(static_cast<int>(new_node_size));
 
   if (owner_->heap()->inline_allocation_disabled()) {
     // Keep the linear allocation area empty if requested to do so, just
     // return area back to the free list instead.
     owner_->Free(new_node->address() + size_in_bytes, bytes_left);
     owner_->SetAllocationInfo(new_node->address() + size_in_bytes,
                               new_node->address() + size_in_bytes);
   } else if (bytes_left > kThreshold &&
              owner_->heap()->incremental_marking()->IsMarkingIncomplete() &&
              FLAG_incremental_marking) {
-    int linear_size = owner_->RoundSizeDownToObjectAlignment(kThreshold);
+    size_t linear_size = owner_->RoundSizeDownToObjectAlignment(kThreshold);
     // We don't want to give too large linear areas to the allocator while
     // incremental marking is going on, because we won't check again whether
     // we want to do another increment until the linear area is used up.
+    DCHECK_GE(new_node_size, size_in_bytes + linear_size);
     owner_->Free(new_node->address() + size_in_bytes + linear_size,
                  new_node_size - size_in_bytes - linear_size);
     owner_->SetAllocationInfo(
         new_node->address() + size_in_bytes,
         new_node->address() + size_in_bytes + linear_size);
   } else {
-    DCHECK(bytes_left >= 0);
     // Normally we give the rest of the node to the allocator as its new
     // linear allocation area.
     owner_->SetAllocationInfo(new_node->address() + size_in_bytes,
                               new_node->address() + new_node_size);
   }
 
   return new_node;
 }
 
-intptr_t FreeList::EvictFreeListItems(Page* page) {
-  intptr_t sum = 0;
+size_t FreeList::EvictFreeListItems(Page* page) {
+  size_t sum = 0;
   page->ForAllFreeListCategories(
       [this, &sum, page](FreeListCategory* category) {
         DCHECK_EQ(this, category->owner());
         sum += category->available();
         RemoveCategory(category);
         category->Invalidate();
       });
   return sum;
 }
 
@@ skipping 53 matching lines @@
          static_cast<void*>(categories_[type]), type);
   while (it.HasNext()) {
     FreeListCategory* current = it.Next();
     PrintF("%p -> ", static_cast<void*>(current));
   }
   PrintF("null\n");
 }
 
 
 #ifdef DEBUG
-intptr_t FreeListCategory::SumFreeList() {
-  intptr_t sum = 0;
+size_t FreeListCategory::SumFreeList() {
+  size_t sum = 0;
   FreeSpace* cur = top();
   while (cur != NULL) {
     DCHECK(cur->map() == cur->GetHeap()->root(Heap::kFreeSpaceMapRootIndex));
     sum += cur->nobarrier_size();
     cur = cur->next();
   }
   return sum;
 }
 
 int FreeListCategory::FreeListLength() {
@@ skipping 16 matching lines @@
       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.
-intptr_t FreeList::SumFreeLists() {
-  intptr_t sum = 0;
+size_t FreeList::SumFreeLists() {
+  size_t sum = 0;
   ForAllFreeListCategories(
       [&sum](FreeListCategory* category) { sum += category->SumFreeList(); });
   return sum;
 }
 #endif
 
 
 // -----------------------------------------------------------------------------
 // OldSpace implementation
 
@@ skipping 18 matching lines @@
 
 // After we have booted, we have created a map which represents free space
 // 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.
   for (Page* page : *this) {
-    int size = static_cast<int>(page->wasted_memory());
+    size_t size = page->wasted_memory();
     if (size == 0) continue;
+    DCHECK_GE(static_cast<size_t>(Page::kPageSize), size);
     Address address = page->OffsetToAddress(Page::kPageSize - size);
-    heap()->CreateFillerObjectAt(address, size, ClearRecordedSlots::kNo);
+    heap()->CreateFillerObjectAt(address, static_cast<int>(size),
+                                 ClearRecordedSlots::kNo);
   }
 }
 
 
 void PagedSpace::EvictEvacuationCandidatesFromLinearAllocationArea() {
   if (allocation_info_.top() >= allocation_info_.limit()) return;
 
   if (!Page::FromAllocationAreaAddress(allocation_info_.top())->CanAllocate()) {
     // Create filler object to keep page iterable if it was iterable.
     int remaining =
@@ skipping 21 matching lines @@
 
 HeapObject* CompactionSpace::SweepAndRetryAllocation(int size_in_bytes) {
   MarkCompactCollector* collector = heap()->mark_compact_collector();
   if (collector->sweeping_in_progress()) {
     collector->SweepAndRefill(this);
     return free_list_.Allocate(size_in_bytes);
   }
   return nullptr;
 }
 
-
 HeapObject* PagedSpace::SlowAllocateRaw(int size_in_bytes) {
   const int kMaxPagesToSweep = 1;
 
   // Allocation in this space has failed.
 
   MarkCompactCollector* collector = heap()->mark_compact_collector();
   // Sweeping is still in progress.
   if (collector->sweeping_in_progress()) {
     // First try to refill the free-list, concurrent sweeper threads
     // may have freed some objects in the meantime.
     RefillFreeList();
 
     // Retry the free list allocation.
-    HeapObject* object = free_list_.Allocate(size_in_bytes);
+    HeapObject* object =
+        free_list_.Allocate(static_cast<size_t>(size_in_bytes));
     if (object != NULL) return object;
 
     // If sweeping is still in progress try to sweep pages on the main thread.
     int max_freed = collector->sweeper().ParallelSweepSpace(
         identity(), size_in_bytes, kMaxPagesToSweep);
     RefillFreeList();
     if (max_freed >= size_in_bytes) {
-      object = free_list_.Allocate(size_in_bytes);
+      object = free_list_.Allocate(static_cast<size_t>(size_in_bytes));
       if (object != nullptr) return object;
     }
   }
 
   if (heap()->ShouldExpandOldGenerationOnAllocationFailure() && Expand()) {
     DCHECK((CountTotalPages() > 1) ||
            (size_in_bytes <= free_list_.Available()));
-    return free_list_.Allocate(size_in_bytes);
+    return free_list_.Allocate(static_cast<size_t>(size_in_bytes));
   }
 
   // If sweeper threads are active, wait for them at that point and steal
   // elements form their free-lists. Allocation may still fail their which
   // would indicate that there is not enough memory for the given allocation.
   return SweepAndRetryAllocation(size_in_bytes);
 }
 
 #ifdef DEBUG
 void PagedSpace::ReportStatistics() {
@@ skipping 99 matching lines @@
                                                Executability executable) {
   // Check if we want to force a GC before growing the old space further.
   // If so, fail the allocation.
   if (!heap()->CanExpandOldGeneration(object_size)) {
     return AllocationResult::Retry(identity());
   }
 
   LargePage* page = heap()->memory_allocator()->AllocateLargePage(
       object_size, this, executable);
   if (page == NULL) return AllocationResult::Retry(identity());
-  DCHECK(page->area_size() >= object_size);
+  DCHECK_GE(page->area_size(), static_cast<size_t>(object_size));
 
   size_ += static_cast<int>(page->size());
   AccountCommitted(page->size());
   objects_size_ += object_size;
   page_count_++;
   page->set_next_page(first_page_);
   first_page_ = page;
 
   InsertChunkMapEntries(page);
 
@@ skipping 245 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 }  // namespace internal
 }  // namespace v8