improve allocation accounting for incremental mark

improve allocation accounting for incremental mark

Add an assertion that allocated_bytes >=0 in IncrementalMark::Step and then
make it pass.

We were not being diligent in maintaining top_on_previous_step_ and as a
result inaccurate, and even negative values of allocated_bytes were being
reported to Step.

I need the value of allocated_bytes allocated on each step to be accurate
to enable some follow-on work I am planning to do.

BUG=
R=hpayer@chromium.org

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

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc
File src/heap/spaces.cc (left):

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#oldcode1489
src/heap/spaces.cc:1489: int bytes_allocated = static_cast<int>(old_top -
top_on_previous_step_);
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.

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#newcode1403
src/heap/spaces.cc:1403: if (top_on_previous_step_) {
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.

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#newcode1478
src/heap/spaces.cc:1478: int aligned_size_in_bytes = size_in_bytes +
alignment_size;
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]

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc
File src/heap/spaces.cc (left):

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#oldcode1489
src/heap/spaces.cc:1489: int bytes_allocated = static_cast<int>(old_top -
top_on_previous_step_);
On 2015/07/23 10:58:54, Hannes Payer wrote:
> 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.

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.

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#newcode1403
src/heap/spaces.cc:1403: if (top_on_previous_step_) {
On 2015/07/23 10:58:54, Hannes Payer wrote:
> 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.

Acknowledged.

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#newcode1478
src/heap/spaces.cc:1478: int aligned_size_in_bytes = size_in_bytes +
alignment_size;
On 2015/07/23 10:58:54, Hannes Payer wrote:
> 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)?

Okay, let me look into this.

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

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#newcode1478
src/heap/spaces.cc:1478: int aligned_size_in_bytes = size_in_bytes +
alignment_size;
On 2015/07/23 16:31:34, ofrobots wrote:
> On 2015/07/23 10:58:54, Hannes Payer wrote:
> > 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)?
> 
> Okay, let me look into this.

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]

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc
File src/heap/spaces.cc (right):

https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#newcode1478
src/heap/spaces.cc:1478: int aligned_size_in_bytes = size_in_bytes +
alignment_size;
On 2015/07/23 17:41:06, ofrobots wrote:
> On 2015/07/23 16:31:34, ofrobots wrote:
> > On 2015/07/23 10:58:54, Hannes Payer wrote:
> > > 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)?
> > 
> > Okay, let me look into this.
> 
> 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.

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?

[ofrobots, 2015-07-29 20:45:06]

On 2015/07/24 06:32:10, Hannes Payer wrote:
> https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc
> File src/heap/spaces.cc (right):
> 
>
https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#newcode1478
> src/heap/spaces.cc:1478: int aligned_size_in_bytes = size_in_bytes +
> alignment_size;
> On 2015/07/23 17:41:06, ofrobots wrote:
> > On 2015/07/23 16:31:34, ofrobots wrote:
> > > On 2015/07/23 10:58:54, Hannes Payer wrote:
> > > > 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)?
> > > 
> > > Okay, let me look into this.
> > 
> > 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.
> 
> 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?

SGTM. Will update the patches.

[ofrobots, 2015-07-29 21:56:00]

On 2015/07/29 20:45:06, ofrobots wrote:
> On 2015/07/24 06:32:10, Hannes Payer wrote:
> > https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc
> > File src/heap/spaces.cc (right):
> > 
> >
>
https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#newcode1478
> > src/heap/spaces.cc:1478: int aligned_size_in_bytes = size_in_bytes +
> > alignment_size;
> > On 2015/07/23 17:41:06, ofrobots wrote:
> > > On 2015/07/23 16:31:34, ofrobots wrote:
> > > > On 2015/07/23 10:58:54, Hannes Payer wrote:
> > > > > 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)?
> > > > 
> > > > Okay, let me look into this.
> > > 
> > > 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.
> > 
> > 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?
> 
> SGTM. Will update the patches.

Decided to make the suggested changes to remove recursion in a separate
change-list https://codereview.chromium.org/1265443003.

Once that is accepted, I will rebase this.

[ofrobots, 2015-08-07 07:20:27]

On 2015/07/29 21:56:00, ofrobots wrote:
> On 2015/07/29 20:45:06, ofrobots wrote:
> > On 2015/07/24 06:32:10, Hannes Payer wrote:
> > > https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc
> > > File src/heap/spaces.cc (right):
> > > 
> > >
> >
>
https://codereview.chromium.org/1252053003/diff/1/src/heap/spaces.cc#newcode1478
> > > src/heap/spaces.cc:1478: int aligned_size_in_bytes = size_in_bytes +
> > > alignment_size;
> > > On 2015/07/23 17:41:06, ofrobots wrote:
> > > > On 2015/07/23 16:31:34, ofrobots wrote:
> > > > > On 2015/07/23 10:58:54, Hannes Payer wrote:
> > > > > > 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)?
> > > > > 
> > > > > Okay, let me look into this.
> > > > 
> > > > 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.
> > > 
> > > 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?
> > 
> > SGTM. Will update the patches.
> 
> Decided to make the suggested changes to remove recursion in a separate
> change-list https://codereview.chromium.org/1265443003.
> 
> Once that is accepted, I will rebase this.

Superceded by https://codereview.chromium.org/1274453002/.