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

src/heap/spaces.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_H_
 #define V8_HEAP_SPACES_H_
 
 #include <list>
 #include <memory>
 #include <unordered_set>
@@ skipping 117 matching lines @@
   kNumberOfCategories = kLastCategory + 1,
   kInvalidCategory
 };
 
 enum FreeMode { kLinkCategory, kDoNotLinkCategory };
 
 // A free list category maintains a linked list of free memory blocks.
 class FreeListCategory {
  public:
   static const int kSize = kIntSize +      // FreeListCategoryType type_
-                           kIntSize +      // int available_
+                           kIntSize +      // padding for type_
+                           kSizetSize +    // size_t available_
                            kPointerSize +  // FreeSpace* top_
                            kPointerSize +  // FreeListCategory* prev_
                            kPointerSize;   // FreeListCategory* next_
 
   FreeListCategory()
       : type_(kInvalidCategory),
         available_(0),
         top_(nullptr),
         prev_(nullptr),
         next_(nullptr) {}
@@ skipping 11 matching lines @@
   void Reset();
 
   void ResetStats() { Reset(); }
 
   void RepairFreeList(Heap* heap);
 
   // Relinks the category into the currently owning free list. Requires that the
   // category is currently unlinked.
   void Relink();
 
-  bool Free(FreeSpace* node, int size_in_bytes, FreeMode mode);
+  bool Free(FreeSpace* node, size_t size_in_bytes, FreeMode mode);
 
   // Picks a node from the list and stores its size in |node_size|. Returns
   // nullptr if the category is empty.
-  FreeSpace* PickNodeFromList(int* node_size);
+  FreeSpace* PickNodeFromList(size_t* node_size);
 
   // Performs a single try to pick a node of at least |minimum_size| from the
   // category. Stores the actual size in |node_size|. Returns nullptr if no
   // node is found.
-  FreeSpace* TryPickNodeFromList(int minimum_size, int* node_size);
+  FreeSpace* TryPickNodeFromList(size_t minimum_size, size_t* node_size);
 
   // Picks a node of at least |minimum_size| from the category. Stores the
   // actual size in |node_size|. Returns nullptr if no node is found.
-  FreeSpace* SearchForNodeInList(int minimum_size, int* node_size);
+  FreeSpace* SearchForNodeInList(size_t minimum_size, size_t* node_size);
 
   inline FreeList* owner();
   inline bool is_linked();
   bool is_empty() { return top() == nullptr; }
-  int available() const { return available_; }
+  size_t available() const { return available_; }
 
 #ifdef DEBUG
-  intptr_t SumFreeList();
+  size_t SumFreeList();
   int FreeListLength();
 #endif
 
  private:
   // For debug builds we accurately compute free lists lengths up until
   // {kVeryLongFreeList} by manually walking the list.
   static const int kVeryLongFreeList = 500;
 
   inline Page* page();
 
   FreeSpace* top() { return top_; }
   void set_top(FreeSpace* top) { top_ = top; }
   FreeListCategory* prev() { return prev_; }
   void set_prev(FreeListCategory* prev) { prev_ = prev; }
   FreeListCategory* next() { return next_; }
   void set_next(FreeListCategory* next) { next_ = next; }
 
   // |type_|: The type of this free list category.
   FreeListCategoryType type_;
 
   // |available_|: Total available bytes in all blocks of this free list
   // category.
-  int available_;
+  size_t available_;
 
   // |top_|: Points to the top FreeSpace* in the free list category.
   FreeSpace* top_;
 
   FreeListCategory* prev_;
   FreeListCategory* next_;
 
   friend class FreeList;
   friend class PagedSpace;
 };
@@ skipping 88 matching lines @@
   static const intptr_t kAlignment =
       (static_cast<uintptr_t>(1) << kPageSizeBits);
 
   static const intptr_t kAlignmentMask = kAlignment - 1;
 
   static const intptr_t kSizeOffset = 0;
 
   static const intptr_t kFlagsOffset = kSizeOffset + kPointerSize;
 
   static const size_t kMinHeaderSize =
-      kSizeOffset + kPointerSize  // size_t size
-      + kIntptrSize               // Flags flags_
-      + kPointerSize              // Address area_start_
-      + kPointerSize              // Address area_end_
-      + 2 * kPointerSize          // base::VirtualMemory reservation_
-      + kPointerSize              // Address owner_
-      + kPointerSize              // Heap* heap_
-      + kIntSize                  // int progress_bar_
-      + kIntSize                  // int live_bytes_count_
-      + kPointerSize              // SlotSet* old_to_new_slots_
-      + kPointerSize              // SlotSet* old_to_old_slots_
-      + kPointerSize              // TypedSlotSet* typed_old_to_new_slots_
-      + kPointerSize              // TypedSlotSet* typed_old_to_old_slots_
-      + kPointerSize              // SkipList* skip_list_
-      + kPointerSize              // AtomicValue high_water_mark_
-      + kPointerSize              // base::Mutex* mutex_
-      + kPointerSize              // base::AtomicWord concurrent_sweeping_
-      + 2 * kPointerSize          // AtomicNumber free-list statistics
-      + kPointerSize              // AtomicValue next_chunk_
-      + kPointerSize              // AtomicValue prev_chunk_
+      kSizeOffset + kSizetSize  // size_t size
+      + kIntptrSize             // Flags flags_
+      + kPointerSize            // Address area_start_
+      + kPointerSize            // Address area_end_
+      + 2 * kPointerSize        // base::VirtualMemory reservation_
+      + kPointerSize            // Address owner_
+      + kPointerSize            // Heap* heap_
+      + kIntSize                // int progress_bar_
+      + kIntSize                // int live_bytes_count_
+      + kPointerSize            // SlotSet* old_to_new_slots_
+      + kPointerSize            // SlotSet* old_to_old_slots_
+      + kPointerSize            // TypedSlotSet* typed_old_to_new_slots_
+      + kPointerSize            // TypedSlotSet* typed_old_to_old_slots_
+      + kPointerSize            // SkipList* skip_list_
+      + kPointerSize            // AtomicValue high_water_mark_
+      + kPointerSize            // base::Mutex* mutex_
+      + kPointerSize            // base::AtomicWord concurrent_sweeping_
+      + 2 * kSizetSize          // AtomicNumber free-list statistics
+      + kPointerSize            // AtomicValue next_chunk_
+      + kPointerSize            // AtomicValue prev_chunk_
       // FreeListCategory categories_[kNumberOfCategories]
       + FreeListCategory::kSize * kNumberOfCategories +
       kPointerSize  // LocalArrayBufferTracker* local_tracker_
       // std::unordered_set<Address>* black_area_end_marker_map_
       + kPointerSize;
 
   // We add some more space to the computed header size to amount for missing
   // alignment requirements in our computation.
   // Try to get kHeaderSize properly aligned on 32-bit and 64-bit machines.
   static const size_t kHeaderSize = kMinHeaderSize;
@@ skipping 99 matching lines @@
   void ReleaseOldToOldSlots();
   void AllocateTypedOldToNewSlots();
   void ReleaseTypedOldToNewSlots();
   void AllocateTypedOldToOldSlots();
   void ReleaseTypedOldToOldSlots();
   void AllocateLocalTracker();
   void ReleaseLocalTracker();
 
   Address area_start() { return area_start_; }
   Address area_end() { return area_end_; }
-  int area_size() { return static_cast<int>(area_end() - area_start()); }
+  size_t area_size() { return static_cast<size_t>(area_end() - area_start()); }
 
   bool CommitArea(size_t requested);
 
   // Approximate amount of physical memory committed for this chunk.
   size_t CommittedPhysicalMemory();
 
   Address HighWaterMark() { return address() + high_water_mark_.Value(); }
 
   int progress_bar() {
     DCHECK(IsFlagSet(HAS_PROGRESS_BAR));
@@ skipping 269 matching lines @@
   void set_prev_page(Page* page) { set_prev_chunk(page); }
 
   template <typename Callback>
   inline void ForAllFreeListCategories(Callback callback) {
     for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
       callback(&categories_[i]);
     }
   }
 
   // Returns the offset of a given address to this page.
-  inline int Offset(Address a) {
-    int offset = static_cast<int>(a - address());
-    return offset;
-  }
+  inline size_t Offset(Address a) { return static_cast<size_t>(a - address()); }
 
   // Returns the address for a given offset to the this page.
-  Address OffsetToAddress(int offset) {
+  Address OffsetToAddress(size_t offset) {
     DCHECK_PAGE_OFFSET(offset);
     return address() + offset;
   }
 
   // WaitUntilSweepingCompleted only works when concurrent sweeping is in
   // progress. In particular, when we know that right before this call a
   // sweeper thread was sweeping this page.
   void WaitUntilSweepingCompleted() {
     mutex_->Lock();
     mutex_->Unlock();
     DCHECK(SweepingDone());
   }
 
   bool SweepingDone() {
     return concurrent_sweeping_state().Value() == kSweepingDone;
   }
 
   void ResetFreeListStatistics();
 
-  int LiveBytesFromFreeList() {
-    return static_cast<int>(area_size() - wasted_memory() -
-                            available_in_free_list());
+  size_t AvailableInFreeList();
+
+  size_t LiveBytesFromFreeList() {
+    DCHECK_GE(area_size(), wasted_memory() + available_in_free_list());
+    return area_size() - wasted_memory() - available_in_free_list();
   }
 
   FreeListCategory* free_list_category(FreeListCategoryType type) {
     return &categories_[type];
   }
 
   bool is_anchor() { return IsFlagSet(Page::ANCHOR); }
 
-  intptr_t wasted_memory() { return wasted_memory_.Value(); }
-  void add_wasted_memory(intptr_t waste) { wasted_memory_.Increment(waste); }
-  intptr_t available_in_free_list() { return available_in_free_list_.Value(); }
-  void add_available_in_free_list(intptr_t available) {
+  size_t wasted_memory() { return wasted_memory_.Value(); }
+  void add_wasted_memory(size_t waste) { wasted_memory_.Increment(waste); }
+  size_t available_in_free_list() { return available_in_free_list_.Value(); }
+  void add_available_in_free_list(size_t available) {
+    DCHECK_LE(available, area_size());
     available_in_free_list_.Increment(available);
   }
+  void remove_available_in_free_list(size_t available) {
+    DCHECK_LE(available, area_size());
+    DCHECK_GE(available_in_free_list(), available);
+    available_in_free_list_.Decrement(available);
+  }
 
   size_t ShrinkToHighWaterMark();
 
 #ifdef DEBUG
   void Print();
 #endif  // DEBUG
 
  private:
   enum InitializationMode { kFreeMemory, kDoNotFreeMemory };
 
@@ skipping 881 matching lines @@
   }
 
   explicit FreeList(PagedSpace* owner);
 
   // Adds a node on the free list. The block of size {size_in_bytes} starting
   // at {start} is placed on the free list. The return value is the number of
   // bytes that were not added to the free list, because they freed memory block
   // was too small. Bookkeeping information will be written to the block, i.e.,
   // its contents will be destroyed. The start address should be word aligned,
   // and the size should be a non-zero multiple of the word size.
-  int Free(Address start, int size_in_bytes, FreeMode mode);
+  size_t Free(Address start, size_t size_in_bytes, FreeMode mode);
 
   // Allocate a block of size {size_in_bytes} from the free list. The block is
   // unitialized. A failure is returned if no block is available. The size
   // should be a non-zero multiple of the word size.
-  MUST_USE_RESULT HeapObject* Allocate(int size_in_bytes);
+  MUST_USE_RESULT HeapObject* Allocate(size_t size_in_bytes);
 
   // Clear the free list.
   void Reset();
 
   void ResetStats() {
     wasted_bytes_.SetValue(0);
     ForAllFreeListCategories(
         [](FreeListCategory* category) { category->ResetStats(); });
   }
 
@@ skipping 10 matching lines @@
     bool empty = true;
     ForAllFreeListCategories([&empty](FreeListCategory* category) {
       if (!category->is_empty()) empty = false;
     });
     return empty;
   }
 
   // Used after booting the VM.
   void RepairLists(Heap* heap);
 
-  intptr_t EvictFreeListItems(Page* page);
+  size_t EvictFreeListItems(Page* page);
   bool ContainsPageFreeListItems(Page* page);
 
   PagedSpace* owner() { return owner_; }
-  intptr_t wasted_bytes() { return wasted_bytes_.Value(); }
+  size_t wasted_bytes() { return wasted_bytes_.Value(); }
 
   template <typename Callback>
   void ForAllFreeListCategories(FreeListCategoryType type, Callback callback) {
     FreeListCategory* current = categories_[type];
     while (current != nullptr) {
       FreeListCategory* next = current->next();
       callback(current);
       current = next;
     }
   }
 
   template <typename Callback>
   void ForAllFreeListCategories(Callback callback) {
     for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
       ForAllFreeListCategories(static_cast<FreeListCategoryType>(i), callback);
     }
   }
 
   bool AddCategory(FreeListCategory* category);
   void RemoveCategory(FreeListCategory* category);
   void PrintCategories(FreeListCategoryType type);
 
 #ifdef DEBUG
-  intptr_t SumFreeLists();
+  size_t SumFreeLists();
   bool IsVeryLong();
 #endif
 
  private:
   class FreeListCategoryIterator {
    public:
     FreeListCategoryIterator(FreeList* free_list, FreeListCategoryType type)
         : current_(free_list->categories_[type]) {}
 
     bool HasNext() { return current_ != nullptr; }
 
     FreeListCategory* Next() {
       DCHECK(HasNext());
       FreeListCategory* tmp = current_;
       current_ = current_->next();
       return tmp;
     }
 
    private:
     FreeListCategory* current_;
   };
 
   // The size range of blocks, in bytes.
-  static const int kMinBlockSize = 3 * kPointerSize;
-  static const int kMaxBlockSize = Page::kAllocatableMemory;
+  static const size_t kMinBlockSize = 3 * kPointerSize;
+  static const size_t kMaxBlockSize = Page::kAllocatableMemory;
 
-  static const int kTiniestListMax = 0xa * kPointerSize;
-  static const int kTinyListMax = 0x1f * kPointerSize;
-  static const int kSmallListMax = 0xff * kPointerSize;
-  static const int kMediumListMax = 0x7ff * kPointerSize;
-  static const int kLargeListMax = 0x3fff * kPointerSize;
-  static const int kTinyAllocationMax = kTiniestListMax;
-  static const int kSmallAllocationMax = kTinyListMax;
-  static const int kMediumAllocationMax = kSmallListMax;
-  static const int kLargeAllocationMax = kMediumListMax;
+  static const size_t kTiniestListMax = 0xa * kPointerSize;
+  static const size_t kTinyListMax = 0x1f * kPointerSize;
+  static const size_t kSmallListMax = 0xff * kPointerSize;
+  static const size_t kMediumListMax = 0x7ff * kPointerSize;
+  static const size_t kLargeListMax = 0x3fff * kPointerSize;
+  static const size_t kTinyAllocationMax = kTiniestListMax;
+  static const size_t kSmallAllocationMax = kTinyListMax;
+  static const size_t kMediumAllocationMax = kSmallListMax;
+  static const size_t kLargeAllocationMax = kMediumListMax;
 
-  FreeSpace* FindNodeFor(int size_in_bytes, int* node_size);
+  FreeSpace* FindNodeFor(size_t size_in_bytes, size_t* node_size);
 
   // Walks all available categories for a given |type| and tries to retrieve
   // a node. Returns nullptr if the category is empty.
-  FreeSpace* FindNodeIn(FreeListCategoryType type, int* node_size);
+  FreeSpace* FindNodeIn(FreeListCategoryType type, size_t* node_size);
 
   // Tries to retrieve a node from the first category in a given |type|.
   // Returns nullptr if the category is empty.
-  FreeSpace* TryFindNodeIn(FreeListCategoryType type, int* node_size,
-                           int minimum_size);
+  FreeSpace* TryFindNodeIn(FreeListCategoryType type, size_t* node_size,
+                           size_t minimum_size);
 
   // Searches a given |type| for a node of at least |minimum_size|.
-  FreeSpace* SearchForNodeInList(FreeListCategoryType type, int* node_size,
-                                 int minimum_size);
+  FreeSpace* SearchForNodeInList(FreeListCategoryType type, size_t* node_size,
+                                 size_t minimum_size);
 
   FreeListCategoryType SelectFreeListCategoryType(size_t size_in_bytes) {
     if (size_in_bytes <= kTiniestListMax) {
       return kTiniest;
     } else if (size_in_bytes <= kTinyListMax) {
       return kTiny;
     } else if (size_in_bytes <= kSmallListMax) {
       return kSmall;
     } else if (size_in_bytes <= kMediumListMax) {
       return kMedium;
@@ skipping 12 matching lines @@
       return kMedium;
     } else if (size_in_bytes <= kLargeAllocationMax) {
       return kLarge;
     }
     return kHuge;
   }
 
   FreeListCategory* top(FreeListCategoryType type) { return categories_[type]; }
 
   PagedSpace* owner_;
-  base::AtomicNumber<intptr_t> wasted_bytes_;
+  base::AtomicNumber<size_t> wasted_bytes_;
   FreeListCategory* categories_[kNumberOfCategories];
 
   friend class FreeListCategory;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList);
 };
 
 // LocalAllocationBuffer represents a linear allocation area that is created
 // from a given {AllocationResult} and can be used to allocate memory without
 // synchronization.
@@ skipping 166 matching lines @@
 
   // Allocate the requested number of bytes in the space and consider allocation
   // alignment if needed.
   MUST_USE_RESULT inline AllocationResult AllocateRaw(
       int size_in_bytes, AllocationAlignment alignment);
 
   // Give a block of memory to the space's free list.  It might be added to
   // the free list or accounted as waste.
   // If add_to_freelist is false then just accounting stats are updated and
   // no attempt to add area to free list is made.
-  int Free(Address start, int size_in_bytes) {
-    int wasted = free_list_.Free(start, size_in_bytes, kLinkCategory);
+  size_t Free(Address start, size_t size_in_bytes) {
+    size_t wasted = free_list_.Free(start, size_in_bytes, kLinkCategory);
     accounting_stats_.DeallocateBytes(size_in_bytes);
+    DCHECK_GE(size_in_bytes, wasted);
     return size_in_bytes - wasted;
   }
 
-  int UnaccountedFree(Address start, int size_in_bytes) {
-    int wasted = free_list_.Free(start, size_in_bytes, kDoNotLinkCategory);
+  size_t UnaccountedFree(Address start, size_t size_in_bytes) {
+    size_t wasted = free_list_.Free(start, size_in_bytes, kDoNotLinkCategory);
+    DCHECK_GE(size_in_bytes, wasted);
     return size_in_bytes - wasted;
   }
 
   void ResetFreeList() { free_list_.Reset(); }
 
   // Set space allocation info.
   void SetTopAndLimit(Address top, Address limit) {
     DCHECK(top == limit ||
            Page::FromAddress(top) == Page::FromAddress(limit - 1));
     MemoryChunk::UpdateHighWaterMark(allocation_info_.top());
@@ skipping 877 matching lines @@
   PageIterator old_iterator_;
   PageIterator code_iterator_;
   PageIterator map_iterator_;
   LargePageIterator lo_iterator_;
 };
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_HEAP_SPACES_H_