improve allocation accounting for incremental mark

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/v8.h"
 
 #include "src/base/bits.h"
 #include "src/base/platform/platform.h"
 #include "src/full-codegen.h"
 #include "src/heap/mark-compact.h"
@@ skipping 1382 matching lines @@
 
 void NewSpace::ResetAllocationInfo() {
   to_space_.Reset();
   UpdateAllocationInfo();
   pages_used_ = 0;
   // Clear all mark-bits in the to-space.
   NewSpacePageIterator it(&to_space_);
   while (it.has_next()) {
     Bitmap::Clear(it.next());
   }
+  if (top_on_previous_step_) {

[Hannes Payer (out of office), 2015/07/23 10:58:54]

Resetting here make the step still imprecise. We are loosing the amount of
memory allocated right before resetting. I am fine with that, i.e. it should not
be a problem for incremental marking. But you have to be aware of that case.
Let's add a comment.

[ofrobots, 2015/07/23 16:31:34]

Acknowledged.

+    // Start a new step.
+    top_on_previous_step_ = allocation_info_.top();
+  }
 }
 
 
 void NewSpace::UpdateInlineAllocationLimit(int size_in_bytes) {
   if (heap()->inline_allocation_disabled()) {
     // Lowest limit when linear allocation was disabled.
     Address high = to_space_.page_high();
     Address new_top = allocation_info_.top() + size_in_bytes;
     allocation_info_.set_limit(Min(new_top, high));
   } else if (inline_allocation_limit_step() == 0) {
@@ skipping 51 matching lines @@
   return true;
 }
 
 
 AllocationResult NewSpace::SlowAllocateRaw(int size_in_bytes,
                                            AllocationAlignment alignment) {
   Address old_top = allocation_info_.top();
   Address high = to_space_.page_high();
   if (allocation_info_.limit() < high) {
     int alignment_size = Heap::GetFillToAlign(old_top, alignment);
     int aligned_size_in_bytes = size_in_bytes + alignment_size;

[Hannes Payer (out of office), 2015/07/23 10:58:54]

I think we do not need the complicated machinery to update new inline allocation
limit. Why don't we just allocate, get the new top pointer after that, perform
the Step, and call UpdateInlineAllocationLimit(0)?

[ofrobots, 2015/07/23 16:31:34]

Okay, let me look into this.

[ofrobots, 2015/07/23 17:41:06]

The reason this complicated machinery exists is to avoid an infinite loop.
Calling allocate first before doing UpdateInlineAllocationLimit makes a
recursive infinite loop between AllocateRaw* and SlowAllocateRaw. To call
UpdateInlineAllocationLimit we need to do this complicated machinery to
guesstimate the aligned_size_in_bytes that the allocation would allocate.

This code is a bit too wacky. The challenge is to find incremental steps to make
it better. 

I stand by my earlier assertion that it does not make a lot of logical sense to
do a step in the `if (AddFreshPage())` clause because there is no clean way to
avoid double counting. One option would be for me to add an argument to
AllocateRaw* to distinguish the recursive call from here in SlowAllocateRate,
but I really dislike that option.

[Hannes Payer (out of office), 2015/07/24 06:32:10]

Arg, yes. That is the reason why it is complicated. OK, let's keep it. This also
complicates the AddFreshPage case. 

Adding a parameter to AllocateRaw to indicate the recursion is not nice.

One way to clean that up would be to get rid of this recursion. SlowAllocateRaw
(renamed to EnsureAllocation) could basically make sure that there is room for
the allocation if possible and could just return to AllocateRaw* which performs
the allocation. I think then it should be possible to account for the right
allocated bytes. Similar cases as before 1) just increase the limit if allowed
2) a new page is needed: don't account for the leftover memory at the end of the
page and the page header. As a result, each call to allocation would just
perform one step and would update the top_on_previous_step counter once. WDYT?

 
     // Either the limit has been lowered because linear allocation was disabled
     // or because incremental marking wants to get a chance to do a step. Set
     // the new limit accordingly.
     Address new_top = old_top + aligned_size_in_bytes;
     int bytes_allocated = static_cast<int>(new_top - top_on_previous_step_);
+
     heap()->incremental_marking()->Step(bytes_allocated,
                                         IncrementalMarking::GC_VIA_STACK_GUARD);
     UpdateInlineAllocationLimit(aligned_size_in_bytes);
+
+    AllocationResult result =
+        (alignment == kWordAligned)
+            ? AllocateRawUnaligned(size_in_bytes)
+            : AllocateRawAligned(size_in_bytes, alignment);
     top_on_previous_step_ = new_top;
-    if (alignment == kWordAligned) return AllocateRawUnaligned(size_in_bytes);
-    return AllocateRawAligned(size_in_bytes, alignment);
+    return result;
   } else if (AddFreshPage()) {
     // Switched to new page. Try allocating again.
-    int bytes_allocated = static_cast<int>(old_top - top_on_previous_step_);

[Hannes Payer (out of office), 2015/07/23 10:58:54]

This code accounted for bytes_allocated before we switch over to a new page.
When you remove that, you are going to account for potentially more memory on
the next Step (because of fragmentation). I do not think we should remove this
code.

[ofrobots, 2015/07/23 16:31:34]

Okay, I understand why this case is here in the first place: to avoid counting
the headers on the new page. Logically it was not making sense why we were doing
a step here because to reach this code we clearly didn't reach the
inline-allocation-limit.

Regardless, independent of the rest of my changes, there was a bug in here.
Consider the scenario where we reach the inline allocation limit and there is no
room left on the current page. In that scenario, we do a IncremetalMark step,
and then allocate using AllocateRaw[Un]Aligned which recursively calls back to
SlowAllocateRaw. This time we will reach the AddFreshPage scenario and try to do
a step again. Depending on whether top_on_previous_step_ was updated before
(original code) or after (my change) AllocateRaw[Un]Aligned, we either 1)
compute a negative bytes allocated or 2) count the same bytes twice.

Logically, this is not a step, but rather we want to discount some part of the
linear allocation that we would otherwise count.

I'll look into if there is a more elegant fix to this taking into account your
other suggestion.

-    heap()->incremental_marking()->Step(bytes_allocated,
-                                        IncrementalMarking::GC_VIA_STACK_GUARD);
-    top_on_previous_step_ = to_space_.page_low();
     if (alignment == kWordAligned) return AllocateRawUnaligned(size_in_bytes);
     return AllocateRawAligned(size_in_bytes, alignment);
   } else {
     return AllocationResult::Retry();
   }
 }
 
 
 #ifdef VERIFY_HEAP
 // We do not use the SemiSpaceIterator because verification doesn't assume
@@ skipping 1636 matching lines @@
     object->ShortPrint();
     PrintF("\n");
   }
   printf(" --------------------------------------\n");
   printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes());
 }
 
 #endif  // DEBUG
 }  // namespace internal
 }  // namespace v8