Reland of "[heap] Add more tasks for parallel compaction"

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 "src/allocation.h"
 #include "src/atomic-utils.h"
 #include "src/base/atomicops.h"
 #include "src/base/bits.h"
 #include "src/base/platform/mutex.h"
 #include "src/flags.h"
 #include "src/hashmap.h"
 #include "src/list.h"
 #include "src/objects.h"
 #include "src/utils.h"
 
 namespace v8 {
 namespace internal {
 
+class CompactionSpaceCollection;
 class Isolate;
 
 // -----------------------------------------------------------------------------
 // Heap structures:
 //
 // A JS heap consists of a young generation, an old generation, and a large
 // object space. The young generation is divided into two semispaces. A
 // scavenger implements Cheney's copying algorithm. The old generation is
 // separated into a map space and an old object space. The map space contains
 // all (and only) map objects, the rest of old objects go into the old space.
@@ skipping 1381 matching lines @@
 
  private:
   // Current allocation top.
   Address top_;
   // Current allocation limit.
   Address limit_;
 };
 
 
 // An abstraction of the accounting statistics of a page-structured space.
-// The 'capacity' of a space is the number of object-area bytes (i.e., not
-// including page bookkeeping structures) currently in the space. The 'size'
-// of a space is the number of allocated bytes, the 'waste' in the space is
-// the number of bytes that are not allocated and not available to
-// allocation without reorganizing the space via a GC (e.g. small blocks due
-// to internal fragmentation, top of page areas in map space), and the bytes
-// 'available' is the number of unallocated bytes that are not waste.  The
-// capacity is the sum of size, waste, and available.
 //
 // The stats are only set by functions that ensure they stay balanced. These
-// functions increase or decrease one of the non-capacity stats in
-// conjunction with capacity, or else they always balance increases and
-// decreases to the non-capacity stats.
+// functions increase or decrease one of the non-capacity stats in conjunction
+// with capacity, or else they always balance increases and decreases to the
+// non-capacity stats.
 class AllocationStats BASE_EMBEDDED {
  public:
   AllocationStats() { Clear(); }
 
   // Zero out all the allocation statistics (i.e., no capacity).
   void Clear() {
     capacity_ = 0;
     max_capacity_ = 0;
     size_ = 0;
     waste_ = 0;
+    borrowed_ = 0;
   }
 
   void ClearSizeWaste() {
     size_ = capacity_;
     waste_ = 0;
   }
 
   // Reset the allocation statistics (i.e., available = capacity with no
   // wasted or allocated bytes).
   void Reset() {
     size_ = 0;
     waste_ = 0;
   }
 
   // Accessors for the allocation statistics.
   intptr_t Capacity() { return capacity_; }
   intptr_t MaxCapacity() { return max_capacity_; }
   intptr_t Size() { return size_; }
   intptr_t Waste() { return waste_; }
+  intptr_t Borrowed() { return borrowed_; }
 
   // Grow the space by adding available bytes.  They are initially marked as
   // being in use (part of the size), but will normally be immediately freed,
   // putting them on the free list and removing them from size_.
   void ExpandSpace(int size_in_bytes) {
     capacity_ += size_in_bytes;
     size_ += size_in_bytes;
     if (capacity_ > max_capacity_) {
       max_capacity_ = capacity_;
     }
     DCHECK(size_ >= 0);
   }
 
   // Shrink the space by removing available bytes.  Since shrinking is done
   // during sweeping, bytes have been marked as being in use (part of the size)
   // and are hereby freed.
   void ShrinkSpace(int size_in_bytes) {
+    DCHECK_GE(size_in_bytes, 0);
     capacity_ -= size_in_bytes;
     size_ -= size_in_bytes;
-    DCHECK(size_ >= 0);
+    DCHECK_GE(size_, 0);
+    DCHECK_GE(capacity_, 0);
   }
 
   // Allocate from available bytes (available -> size).
   void AllocateBytes(intptr_t size_in_bytes) {
+    DCHECK_GE(size_in_bytes, 0);
     size_ += size_in_bytes;
-    DCHECK(size_ >= 0);
+    DCHECK_GE(size_, 0);
+    DCHECK_LE(size_, capacity_);
   }
 
   // Free allocated bytes, making them available (size -> available).
   void DeallocateBytes(intptr_t size_in_bytes) {
     size_ -= size_in_bytes;
     DCHECK(size_ >= 0);
   }
 
   // Waste free bytes (available -> waste).
   void WasteBytes(int size_in_bytes) {
     DCHECK(size_in_bytes >= 0);
     waste_ += size_in_bytes;
   }
 
   // Merge {other} into {this}.
   void Merge(const AllocationStats& other) {
+    DCHECK_GE(other.capacity_, 0);
+    DCHECK_GE(other.size_, 0);
+    DCHECK_GE(other.waste_, 0);
     capacity_ += other.capacity_;
     size_ += other.size_;
+    // See description of |borrowed_| below why we need to remove it from
+    // |capacity_| as well as |size_|.
+    capacity_ -= other.borrowed_;
+    size_ -= other.borrowed_;
     waste_ += other.waste_;
-    if (other.max_capacity_ > max_capacity_) {
-      max_capacity_ = other.max_capacity_;
+    if (capacity_ > max_capacity_) {
+      max_capacity_ = capacity_;
     }
   }
 
   void DecreaseCapacity(intptr_t size_in_bytes) {
+    DCHECK_GE(size_in_bytes, 0);
     capacity_ -= size_in_bytes;
-    DCHECK_GE(capacity_, 0);
+    DCHECK_GE(capacity_, size_);
   }
 
-  void IncreaseCapacity(intptr_t size_in_bytes) { capacity_ += size_in_bytes; }
+  void IncreaseCapacity(intptr_t size_in_bytes) {
+    DCHECK_GE(size_in_bytes, 0);
+    capacity_ += size_in_bytes;
+  }
+
+  void BorrowMemory(intptr_t size_in_bytes) {
+    DCHECK_GE(size_in_bytes, 0);
+    borrowed_ += size_in_bytes;
+  }
 
  private:
+  // |capacity_| is the number of object-area bytes (i.e., not including page
+  // bookkeeping structures) currently in the space.
   intptr_t capacity_;
+
+  // |max_capacity_| is the maximum |capacity_| ever observed by a space.
   intptr_t max_capacity_;
+
+  // |size_| is the number of allocated bytes.
   intptr_t size_;
+
+  // |waste_| is the number of bytes that are not allocated and not available
+  // to allocation without reorganizing the space via a GC (e.g. small blocks
+  // due to internal fragmentation, top of page areas in map space
   intptr_t waste_;
+
+  // |borrowed_| denotes the number of bytes that are currently borrowed in this
+  // space, i.e., they have been accounted as allocated in another space, but
+  // have been moved over (e.g. through a free list) to the current space.
+  // Note that accounting them as allocated results in them being included
+  // in |size_| as well as |capacity_| of the original space. The temporary
+  // double-accounting is fixed upon merging accounting stats.
+  intptr_t borrowed_;
 };
 
 
 // -----------------------------------------------------------------------------
 // Free lists for old object spaces
 
 // The free list category holds a pointer to the top element and a pointer to
 // the end element of the linked list of free memory blocks.
 class FreeListCategory {
  public:
@@ skipping 138 matching lines @@
   bool ContainsPageFreeListItems(Page* p);
 
   FreeListCategory* small_list() { return &small_list_; }
   FreeListCategory* medium_list() { return &medium_list_; }
   FreeListCategory* large_list() { return &large_list_; }
   FreeListCategory* huge_list() { return &huge_list_; }
 
   PagedSpace* owner() { return owner_; }
 
  private:
+  enum FreeListCategoryType { kSmall, kMedium, kLarge, kHuge };
+
   // The size range of blocks, in bytes.
   static const int kMinBlockSize = 3 * kPointerSize;
   static const int kMaxBlockSize = Page::kMaxRegularHeapObjectSize;
 
   static const int kSmallListMin = 0x1f * kPointerSize;
   static const int kSmallListMax = 0xff * kPointerSize;
   static const int kMediumListMax = 0x7ff * kPointerSize;
   static const int kLargeListMax = 0x3fff * kPointerSize;
   static const int kSmallAllocationMax = kSmallListMin;
   static const int kMediumAllocationMax = kSmallListMax;
   static const int kLargeAllocationMax = kMediumListMax;
 
   FreeSpace* FindNodeFor(int size_in_bytes, int* node_size);
+  FreeSpace* FindNodeIn(FreeListCategoryType category, int* node_size);
+
+  FreeListCategory* GetFreeListCategory(FreeListCategoryType category) {
+    switch (category) {
+      case kSmall:
+        return &small_list_;
+      case kMedium:
+        return &medium_list_;
+      case kLarge:
+        return &large_list_;
+      case kHuge:
+        return &huge_list_;
+      default:
+        UNREACHABLE();
+    }
+    UNREACHABLE();
+    return nullptr;
+  }
+
+  void UpdateFragmentationStats(FreeListCategoryType category, Address address,
+                                int size);
 
   PagedSpace* owner_;
   Heap* heap_;
   FreeListCategory small_list_;
   FreeListCategory medium_list_;
   FreeListCategory large_list_;
   FreeListCategory huge_list_;
 
+  friend class PagedSpace;
+
   DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList);
 };
 
 
 class AllocationResult {
  public:
   // Implicit constructor from Object*.
   AllocationResult(Object* object)  // NOLINT
       : object_(object) {
     // AllocationResults can't return Smis, which are used to represent
@@ skipping 262 matching lines @@
   inline int AreaSize() { return area_size_; }
 
   // Merges {other} into the current space. Note that this modifies {other},
   // e.g., removes its bump pointer area and resets statistics.
   void MergeCompactionSpace(CompactionSpace* other);
 
   void MoveOverFreeMemory(PagedSpace* other);
 
   virtual bool is_local() { return false; }
 
+  // Divide {this} free lists up among {other} CompactionSpaceCollections
+  // up to some certain {limit} of bytes. Note that this operation eventually
+  // needs to iterate over nodes one-by-one, making it a potentially slow
+  // operation.
+  void DivideMemory(CompactionSpaceCollection** other, int num, intptr_t limit);
+
  protected:
+  // Adds memory starting at {start} of {size_in_bytes} to the space.
+  void AddMemory(Address start, int size_in_bytes) {
+    IncreaseCapacity(size_in_bytes);
+    accounting_stats_.BorrowMemory(size_in_bytes);
+    Free(start, size_in_bytes);
+  }
+
+  // Tries to remove some memory from {this} free lists. We try to remove
+  // as much memory as possible, i.e., we check the free lists from huge
+  // to small.
+  FreeSpace* TryRemoveMemory();
+
   // PagedSpaces that should be included in snapshots have different, i.e.,
   // smaller, initial pages.
   virtual bool snapshotable() { return true; }
 
   FreeList* free_list() { return &free_list_; }
 
   bool HasPages() { return anchor_.next_page() != &anchor_; }
 
   // Cleans up the space, frees all pages in this space except those belonging
   // to the initial chunk, uncommits addresses in the initial chunk.
@@ skipping 735 matching lines @@
 };
 
 // -----------------------------------------------------------------------------
 // Compaction space that is used temporarily during compaction.
 
 class CompactionSpace : public PagedSpace {
  public:
   CompactionSpace(Heap* heap, AllocationSpace id, Executability executable)
       : PagedSpace(heap, id, executable) {}
 
-  // Adds external memory starting at {start} of {size_in_bytes} to the space.
-  void AddExternalMemory(Address start, int size_in_bytes) {
-    IncreaseCapacity(size_in_bytes);
-    Free(start, size_in_bytes);
-  }
-
   virtual bool is_local() { return true; }
 
  protected:
   // The space is temporary and not included in any snapshots.
   virtual bool snapshotable() { return false; }
 };
 
 
 // A collection of |CompactionSpace|s used by a single compaction task.
 class CompactionSpaceCollection : public Malloced {
@@ skipping 215 matching lines @@
     count = 0;
   }
   // Must be small, since an iteration is used for lookup.
   static const int kMaxComments = 64;
 };
 #endif
 }
 }  // namespace v8::internal
 
 #endif  // V8_HEAP_SPACES_H_