[Heap profiler] Add construction stack trace to heap object

AllocationTracker now maintains a map from address range to stack trace that allocated the range. When snapshot is generated the map is used to find construction stack trace for an object using its address.

BUG=chromium:277984
LOG=Y
R=alph@chromium.org, mstarzinger@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=19728

[alph, 2014-03-06 14:43:18]

lgtm

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.cc
File src/allocation-tracker.cc (right):

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.c...
src/allocation-tracker.cc:148: ranges_.insert(RangeMap::value_type(start,
new_range));
I have a feeling that using the 'end' address as a key might simplify the lookup
algorithm.

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.c...
src/allocation-tracker.cc:157: if (it->first <= addr && addr < it->second.end) {
it->first <= addr seems to be always true.

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.c...
src/allocation-tracker.cc:163: if (it->first == addr) return
it->second.trace_node_id;
if you use upper_bound instead you won't need to do this check.

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.c...
src/allocation-tracker.cc:166: if (it->first <= addr && addr < it->second.end) {
ditto for it->first <= addr

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.c...
src/allocation-tracker.cc:220: while (it != ranges_.end() &&  it->first < end) {
extra space

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.h
File src/allocation-tracker.h (right):

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.h...
src/allocation-tracker.h:93: void Print();
I think it should be put behind OBJECT_PRINT

https://codereview.chromium.org/177983003/diff/20001/src/heap-snapshot-genera...
File src/heap-snapshot-generator.cc (right):

https://codereview.chromium.org/177983003/diff/20001/src/heap-snapshot-genera...
src/heap-snapshot-generator.cc:402: if (from == to) return false;
true?

https://codereview.chromium.org/177983003/diff/20001/src/heap-snapshot-genera...
src/heap-snapshot-generator.cc:2659: // type, name, id, self_size,
children_index, trace_node_id.
children_index -> edge_count ;-)

[yurys, 2014-03-06 15:38:49]

ptal

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.cc
File src/allocation-tracker.cc (right):

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.c...
src/allocation-tracker.cc:148: ranges_.insert(RangeMap::value_type(start,
new_range));
On 2014/03/06 14:43:18, alph wrote:
> I have a feeling that using the 'end' address as a key might simplify the
lookup
> algorithm.

Good point, thank you! I rewrote this part to use interval end as key.

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.c...
src/allocation-tracker.cc:157: if (it->first <= addr && addr < it->second.end) {
On 2014/03/06 14:43:18, alph wrote:
> it->first <= addr seems to be always true.

This code is gone.

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.c...
src/allocation-tracker.cc:163: if (it->first == addr) return
it->second.trace_node_id;
On 2014/03/06 14:43:18, alph wrote:
> if you use upper_bound instead you won't need to do this check.

Done.

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.c...
src/allocation-tracker.cc:166: if (it->first <= addr && addr < it->second.end) {
On 2014/03/06 14:43:18, alph wrote:
> ditto for it->first <= addr

Done.

https://codereview.chromium.org/177983003/diff/20001/src/allocation-tracker.c...
src/allocation-tracker.cc:220: while (it != ranges_.end() &&  it->first < end) {
On 2014/03/06 14:43:18, alph wrote:
> extra space

Done.

https://codereview.chromium.org/177983003/diff/20001/src/heap-snapshot-genera...
File src/heap-snapshot-generator.cc (right):

https://codereview.chromium.org/177983003/diff/20001/src/heap-snapshot-genera...
src/heap-snapshot-generator.cc:402: if (from == to) return false;
On 2014/03/06 14:43:18, alph wrote:
> true?

We handle object size update in UpdateObjectSize method and shouldn' come here
if the size has changed. We conservatively tell the caller that nothing has
changed in the map.

https://codereview.chromium.org/177983003/diff/20001/src/heap-snapshot-genera...
src/heap-snapshot-generator.cc:2659: // type, name, id, self_size,
children_index, trace_node_id.
On 2014/03/06 14:43:18, alph wrote:
> children_index -> edge_count ;-)

Done.

[yurys, 2014-03-06 15:46:02]

@mstarzinger: please do OWNERS review

[alph, 2014-03-06 16:11:00]

https://codereview.chromium.org/177983003/diff/60001/src/allocation-tracker.cc
File src/allocation-tracker.cc (right):

https://codereview.chromium.org/177983003/diff/60001/src/allocation-tracker.c...
src/allocation-tracker.cc:195: do {
Could you please rewrite do-while to something like:

for (; it != ranges_.end() && it->first <= end; ++it) { }
if (it->second.start < end) {
  it->second.start = end;
}

[yurys, 2014-03-06 16:25:36]

https://codereview.chromium.org/177983003/diff/60001/src/allocation-tracker.cc
File src/allocation-tracker.cc (right):

https://codereview.chromium.org/177983003/diff/60001/src/allocation-tracker.c...
src/allocation-tracker.cc:195: do {
On 2014/03/06 16:11:01, alph wrote:
> Could you please rewrite do-while to something like:
> 
> for (; it != ranges_.end() && it->first <= end; ++it) { }
> if (it->second.start < end) {
>   it->second.start = end;
> }

I started with that but it was one unnecessary check it != ranges_.end(). Also
your code misses it != ranges_.end() check in the if. So I'd leave it as is.

[alph, 2014-03-06 16:26:14]

lgtm

[Michael Starzinger, 2014-03-07 09:15:15]

LGTM.

[yurys, 2014-03-07 16:13:32]

Committed patchset #6 manually as r19728 (presubmit successful).