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 1404 matching lines @@
 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) {

[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) { 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:
   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_;
 };
 
 
 // -----------------------------------------------------------------------------
 // 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 719 matching lines @@
 
   HistogramInfo* allocated_histogram_;
   HistogramInfo* promoted_histogram_;
 
   bool EnsureAllocation(int size_in_bytes, AllocationAlignment alignment);
 
   // If we are doing inline allocation in steps, this method performs the 'step'
   // operation. Right now incremental marking is the only consumer of inline
   // allocation steps. top is the memory address of the bump pointer at the last
   // inline allocation (i.e. it determines the numbers of bytes actually
   // allocated since the last step.) new_top is the address of the bump pointer

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

This is not from your cl.

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

Ack. The baseline did not contain the fixes. Sorry for the troubles.

   // where the next byte is going to be allocated from. top and new_top may be
   // different when we cross a page boundary or reset the space.
   void InlineAllocationStep(Address top, Address new_top);
 
   friend class SemiSpaceIterator;
 };
 
 // -----------------------------------------------------------------------------
 // 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_