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

src/heap/spaces.h

Index: src/heap/spaces.h
diff --git a/src/heap/spaces.h b/src/heap/spaces.h
index 2cea06673abf136a0e3b013680e2cc6d59418e71..b4ead65b30008acdaebfcd58b3b637e6bad0fd5d 100644
--- a/src/heap/spaces.h
+++ b/src/heap/spaces.h
@@ -19,6 +19,7 @@
 namespace v8 {
 namespace internal {
 
+class CompactionSpaceCollection;
 class Isolate;
 
 // -----------------------------------------------------------------------------
@@ -1443,6 +1444,7 @@ class AllocationStats BASE_EMBEDDED {
     max_capacity_ = 0;
     size_ = 0;
     waste_ = 0;
+    borrowed_ = 0;
   }
 
   void ClearSizeWaste() {
@@ -1462,6 +1464,7 @@ class AllocationStats BASE_EMBEDDED {
   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,
@@ -1479,15 +1482,19 @@ class AllocationStats BASE_EMBEDDED {
   // 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).
@@ -1504,26 +1511,44 @@ class AllocationStats BASE_EMBEDDED {
 
   // Merge {other} into {this}.
   void Merge(const AllocationStats& other) {

[Hannes Payer (out of office), 2015/09/25 13:15:59]

Why don't you reset the borrowed counter?

[Michael Lippautz, 2015/09/25 13:28:50]

The caller needs to make sure that the counters are properly "reset". You are
right though, because we only call Reset() and not Clear() in
MergeCompactionSpace().

The whole data structure is set up in a way that callers ensure consistency
(which is the hard part).

+    DCHECK_GE(other.capacity_, 0);
+    DCHECK_GE(other.size_, 0);
+    DCHECK_GE(other.waste_, 0);
     capacity_ += other.capacity_;
     size_ += other.size_;
+    // Since borrowed memory is accounted as capacity by the space borrowing it,
+    // we need to account for this when merging the stats.
+    capacity_ -= other.borrowed_;

[Hannes Payer (out of office), 2015/09/25 13:15:59]

Why do you subtract it from both? Can you explain that in a comment?

[Michael Lippautz, 2015/09/25 13:28:50]

The reason is:
 - The borrowed amount is accounted as allocated (size_) in the original space.
We do not decrease capacity_ (and thus prohibit accounting for it in size_) of
the original space to keep the invariante of SizeOfObjects() > 0 at all times.
 - The borrowed amount is accounted as "borrowed_" in the destination space.
This recording is needed to properly undo the operation while merging.
 - The borrowed amount also increases the capacity of the destination space,
i.e., the borrowed amount can be used for further allocation (thus increasing
also size_ of the destination spacE).

Upon merging we need to make sure that we account for the "double-accounting" of
allocated space by decreasing it from size_, but also capacity_.

[Hannes Payer (out of office), 2015/09/25 14:11:07]

This is really complicated. Can you make your comment more precise?

Overall, the counters are really tricky to get right. We should clean that up at
some point.

[Michael Lippautz, 2015/09/25 14:31:39]

I added some more explanation to the actual member description.

+    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);

[Hannes Payer (out of office), 2015/09/25 13:04:51]

DCHECK_GE(capacity_, 0); is not needed.

[Michael Lippautz, 2015/09/25 13:28:50]

Done.

+    DCHECK_GE(capacity_, size_);
+  }
+
+  void IncreaseCapacity(intptr_t size_in_bytes) {
+    DCHECK_GE(size_in_bytes, 0);
+    capacity_ += size_in_bytes;
   }
 
-  void IncreaseCapacity(intptr_t size_in_bytes) { capacity_ += size_in_bytes; }
+  void BorrowMemory(intptr_t size_in_bytes) {
+    DCHECK_GE(size_in_bytes, 0);
+    borrowed_ += size_in_bytes;
+  }
 
  private:
   intptr_t capacity_;

[Hannes Payer (out of office), 2015/09/25 13:04:51]

Can you add comments that explain these variables?

[Michael Lippautz, 2015/09/25 13:28:50]

The variables are explained on top of the class. Should I move their description
in here?

[Hannes Payer (out of office), 2015/09/25 14:11:07]

No, that is fine. An explanation of borrowed_ is missing than.

[Michael Lippautz, 2015/09/25 14:31:39]

Changed my mind on this. I moved the descriptions of the fields down, added the
one for borrowed_, and kept the general description of the class at the top.

   intptr_t max_capacity_;
   intptr_t size_;
   intptr_t waste_;
+  intptr_t borrowed_;
 };
 
 
@@ -1682,6 +1707,8 @@ class FreeList {
   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;
@@ -1695,6 +1722,27 @@ class FreeList {
   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_;
@@ -1703,6 +1751,8 @@ class FreeList {
   FreeListCategory large_list_;
   FreeListCategory huge_list_;
 
+  friend class PagedSpace;
+
   DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList);
 };
 
@@ -1985,7 +2035,25 @@ class PagedSpace : public Space {
 
   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; }
@@ -2741,12 +2809,6 @@ class CompactionSpace : public PagedSpace {
   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: