[heap] Divide available memory upon compaction tasks

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 "src/base/bits.h"
 #include "src/base/platform/platform.h"
 #include "src/full-codegen/full-codegen.h"
 #include "src/heap/slots-buffer.h"
@@ skipping 964 matching lines @@
   PageIterator iterator(this);
   while (iterator.has_next()) {
     heap()->isolate()->memory_allocator()->Free(iterator.next());
   }
   anchor_.set_next_page(&anchor_);
   anchor_.set_prev_page(&anchor_);
   accounting_stats_.Clear();
 }
 
 
+void PagedSpace::AddMemory(Address start, intptr_t size) {
+  accounting_stats_.ExpandSpace(static_cast<int>(size));
+  Free(start, static_cast<int>(size));
+}
+
+
+FreeSpace* PagedSpace::TryRemoveMemory(intptr_t size_in_bytes) {
+  FreeSpace* space = free_list()->TryRemoveMemory(size_in_bytes);
+  if (space != nullptr) {
+    accounting_stats_.DecreaseCapacity(space->size());
+  }
+  return space;
+}
+
+
+void PagedSpace::DivideUponCompactionSpaces(CompactionSpaceCollection** other,
+                                            int num, intptr_t limit) {
+  DCHECK_GT(num, 0);
+  DCHECK(other != nullptr);
+
+  if (limit == 0) limit = std::numeric_limits<intptr_t>::max();
+
+  EmptyAllocationInfo();
+
+  int index = 0;
+  FreeSpace* node = nullptr;
+  // We evenly distribute existing memory among compaction spaces, i.e., while
+  // iterating over them in round-robin fashion, we check whether they have
+  // reached the {limit} of available bytes and try to add some memory if not.
+  for (CompactionSpace* space = other[index]->Get(identity());

[ulan, 2015/10/09 11:48:48]

Let's simplify the "for" statement so that the correctness is more obvious.

Is it intended that we early exit from the loop as soon as one space is filled?

If not, consider something like:
while (there_is_free_space && not_all_spaces_filled) {
  for (int i = 0; i < num; i++) {
     try_fill_in(space[i]);
  }  
}

[Michael Lippautz, 2015/10/09 12:20:13]

Done, rewrote the loop.

The intention is summarized by your suggestion: keep going in dividing memory as
long as there is either no memory available or all spaces are satisfied.

+       (space->free_list()->available() < limit) &&
+       ((node = TryRemoveMemory(limit - space->free_list()->available())) !=
+        nullptr);
+       space = other[++index % num]->Get(identity())) {
+    CHECK(space->identity() == identity());
+    space->AddMemory(node->address(), node->size());
+  }
+}
+
+
 void PagedSpace::MoveOverFreeMemory(PagedSpace* other) {
   DCHECK(identity() == other->identity());
   // Destroy the linear allocation space of {other}. This is needed to
   //   (a) not waste the memory and
   //   (b) keep the rest of the chunk in an iterable state (filler is needed).
   other->EmptyAllocationInfo();
 
   // Move over the free list. Concatenate makes sure that the source free list
   // gets properly reset after moving over all nodes.
   intptr_t added = free_list_.Concatenate(other->free_list());
 
   // Moved memory is not recorded as allocated memory, but rather increases and
-  // decreases capacity of the corresponding spaces. Used size and waste size
-  // are maintained by the receiving space upon allocating and freeing blocks.
+  // decreases capacity of the corresponding spaces.
   other->accounting_stats_.DecreaseCapacity(added);
   accounting_stats_.IncreaseCapacity(added);
 }
 
 
 void PagedSpace::MergeCompactionSpace(CompactionSpace* other) {
   // Unmerged fields:
   //   area_size_
-  //   allocation_info_
-  //   end_of_unswept_pages_
-  //   unswept_free_bytes_
   //   anchor_
 
   MoveOverFreeMemory(other);
 
   // Update and clear accounting statistics.
   accounting_stats_.Merge(other->accounting_stats_);
-  other->accounting_stats_.Reset();
+  other->accounting_stats_.Clear();
+
+  // The linear allocation area of {other} should be destroyed now.
+  DCHECK(other->top() == nullptr);
+  DCHECK(other->limit() == nullptr);
+
+  DCHECK(other->end_of_unswept_pages_ == nullptr);
 
   AccountCommitted(other->CommittedMemory());
 
   // Move over pages.
   PageIterator it(other);
   Page* p = nullptr;
   while (it.has_next()) {
     p = it.next();
     p->Unlink();
     p->set_owner(this);
@@ skipping 1358 matching lines @@
       page = Page::FromAddress(node->address());
       page->add_available_in_large_free_list(-(*node_size));
     }
   }
 
   DCHECK(IsVeryLong() || available() == SumFreeLists());
   return node;
 }
 
 
+FreeSpace* FreeList::TryRemoveMemory(intptr_t size_in_bytes) {

[ulan, 2015/10/09 11:48:48]

Could you please comment the postconditions of this function?
When node == nullptr is returned, how node.size relates to size_in_bytes.

[Michael Lippautz, 2015/10/09 12:20:13]

Done. I added a high-level description to the .h file. Also I renamed the
parameter to hint_...., as the parameter is rather a hint than actually
enforcing anything.

+  base::LockGuard<base::Mutex> guard(&mutex_);
+  FreeSpace* node = nullptr;
+  int node_size = 0;
+  // Try to find a node that fits exactly.
+  node = FindNodeFor(static_cast<int>(size_in_bytes), &node_size);
+  // If no node could be found get as much memory as possible.
+  if (node == nullptr) node = FindNodeIn(kHuge, &node_size);
+  if (node == nullptr) node = FindNodeIn(kLarge, &node_size);
+  if (node == nullptr) node = FindNodeIn(kMedium, &node_size);
+  if (node == nullptr) node = FindNodeIn(kSmall, &node_size);
+  if (node != nullptr) {
+    // Give back left overs that were not required by {size_in_bytes}.

[Michael Lippautz, 2015/10/09 11:08:59]

This could potentially increase fragmentation, but would allow for more tasks to
share a few huge nodes. During bencmarking (telemetry, smoothness) I found that
creating more tasks speeds up the process almost linearly, but results in #tasks
> #huge nodes, which potentially increases memory (as we need to Expand() in
those tasks).

+    intptr_t aligned_size = RoundUp(size_in_bytes, kPointerSize);
+    intptr_t left_over = node_size - aligned_size;
+    if (left_over > 0) {
+      Free(node->address() + aligned_size, static_cast<int>(left_over));
+      node->set_size(static_cast<int>(aligned_size));
+    }
+  }
+  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);
   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);
@@ skipping 753 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 }  // namespace internal
 }  // namespace v8