CSE2410 Fall 2014 Bounce

// Copyright 2013 the V8 project authors. All rights reserved.

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

//     * Redistributions of source code must retain the above copyright

//       notice, this list of conditions and the following disclaimer.

//     * Redistributions in binary form must reproduce the above

//       copyright notice, this list of conditions and the following

//       disclaimer in the documentation and/or other materials provided

//       with the distribution.

//     * Neither the name of Google Inc. nor the names of its

//       contributors may be used to endorse or promote products derived

//       from this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "v8.h"

#include "heap-snapshot-generator-inl.h"

#include "allocation-tracker.h"

#include "heap-profiler.h"

#include "debug.h"

#include "types.h"

namespace v8 {

namespace internal {

HeapGraphEdge::HeapGraphEdge(Type type, const char* name, int from, int to)

    : type_(type),

      from_index_(from),

      to_index_(to),

      name_(name) {

  ASSERT(type == kContextVariable

      || type == kProperty

      || type == kInternal

      || type == kShortcut);

}

HeapGraphEdge::HeapGraphEdge(Type type, int index, int from, int to)

    : type_(type),

      from_index_(from),

      to_index_(to),

      index_(index) {

  ASSERT(type == kElement || type == kHidden || type == kWeak);

}

void HeapGraphEdge::ReplaceToIndexWithEntry(HeapSnapshot* snapshot) {

  to_entry_ = &snapshot->entries()[to_index_];

}

const int HeapEntry::kNoEntry = -1;

HeapEntry::HeapEntry(HeapSnapshot* snapshot,

                     Type type,

                     const char* name,

                     SnapshotObjectId id,

                     int self_size)

    : type_(type),

      children_count_(0),

      children_index_(-1),

      self_size_(self_size),

      id_(id),

      snapshot_(snapshot),

      name_(name) { }

void HeapEntry::SetNamedReference(HeapGraphEdge::Type type,

                                  const char* name,

                                  HeapEntry* entry) {

  HeapGraphEdge edge(type, name, this->index(), entry->index());

  snapshot_->edges().Add(edge);

  ++children_count_;

}

void HeapEntry::SetIndexedReference(HeapGraphEdge::Type type,

                                    int index,

                                    HeapEntry* entry) {

  HeapGraphEdge edge(type, index, this->index(), entry->index());

  snapshot_->edges().Add(edge);

  ++children_count_;

}

Handle<HeapObject> HeapEntry::GetHeapObject() {

  return snapshot_->collection()->FindHeapObjectById(id());

}

void HeapEntry::Print(

    const char* prefix, const char* edge_name, int max_depth, int indent) {

  STATIC_CHECK(sizeof(unsigned) == sizeof(id()));

  OS::Print("%6d @%6u %*c %s%s: ",

            self_size(), id(), indent, ' ', prefix, edge_name);

  if (type() != kString) {

    OS::Print("%s %.40s\n", TypeAsString(), name_);

  } else {

    OS::Print("\"");

    const char* c = name_;

    while (*c && (c - name_) <= 40) {

      if (*c != '\n')

        OS::Print("%c", *c);

      else

        OS::Print("\\n");

      ++c;

    }

    OS::Print("\"\n");

  }

  if (--max_depth == 0) return;

  Vector<HeapGraphEdge*> ch = children();

  for (int i = 0; i < ch.length(); ++i) {

    HeapGraphEdge& edge = *ch[i];

    const char* edge_prefix = "";

    EmbeddedVector<char, 64> index;

    const char* edge_name = index.start();

    switch (edge.type()) {

      case HeapGraphEdge::kContextVariable:

        edge_prefix = "#";

        edge_name = edge.name();

        break;

      case HeapGraphEdge::kElement:

        OS::SNPrintF(index, "%d", edge.index());

        break;

      case HeapGraphEdge::kInternal:

        edge_prefix = "$";

        edge_name = edge.name();

        break;

      case HeapGraphEdge::kProperty:

        edge_name = edge.name();

        break;

      case HeapGraphEdge::kHidden:

        edge_prefix = "$";

        OS::SNPrintF(index, "%d", edge.index());

        break;

      case HeapGraphEdge::kShortcut:

        edge_prefix = "^";

        edge_name = edge.name();

        break;

      case HeapGraphEdge::kWeak:

        edge_prefix = "w";

        OS::SNPrintF(index, "%d", edge.index());

        break;

      default:

        OS::SNPrintF(index, "!!! unknown edge type: %d ", edge.type());

    }

    edge.to()->Print(edge_prefix, edge_name, max_depth, indent + 2);

  }

}

const char* HeapEntry::TypeAsString() {

  switch (type()) {

    case kHidden: return "/hidden/";

    case kObject: return "/object/";

    case kClosure: return "/closure/";

    case kString: return "/string/";

    case kCode: return "/code/";

    case kArray: return "/array/";

    case kRegExp: return "/regexp/";

    case kHeapNumber: return "/number/";

    case kNative: return "/native/";

    case kSynthetic: return "/synthetic/";

    case kConsString: return "/concatenated string/";

    case kSlicedString: return "/sliced string/";

    default: return "???";

  }

}

// It is very important to keep objects that form a heap snapshot

// as small as possible.

namespace {  // Avoid littering the global namespace.

template <size_t ptr_size> struct SnapshotSizeConstants;

template <> struct SnapshotSizeConstants<4> {

  static const int kExpectedHeapGraphEdgeSize = 12;

  static const int kExpectedHeapEntrySize = 24;

};

template <> struct SnapshotSizeConstants<8> {

  static const int kExpectedHeapGraphEdgeSize = 24;

  static const int kExpectedHeapEntrySize = 32;

};

}  // namespace

HeapSnapshot::HeapSnapshot(HeapSnapshotsCollection* collection,

                           const char* title,

                           unsigned uid)

    : collection_(collection),

      title_(title),

      uid_(uid),

      root_index_(HeapEntry::kNoEntry),

      gc_roots_index_(HeapEntry::kNoEntry),

      natives_root_index_(HeapEntry::kNoEntry),

      max_snapshot_js_object_id_(0) {

  STATIC_CHECK(

      sizeof(HeapGraphEdge) ==

      SnapshotSizeConstants<kPointerSize>::kExpectedHeapGraphEdgeSize);

  STATIC_CHECK(

      sizeof(HeapEntry) ==

      SnapshotSizeConstants<kPointerSize>::kExpectedHeapEntrySize);

  for (int i = 0; i < VisitorSynchronization::kNumberOfSyncTags; ++i) {

    gc_subroot_indexes_[i] = HeapEntry::kNoEntry;

  }

}

void HeapSnapshot::Delete() {

  collection_->RemoveSnapshot(this);

  delete this;

}

void HeapSnapshot::RememberLastJSObjectId() {

  max_snapshot_js_object_id_ = collection_->last_assigned_id();

}

HeapEntry* HeapSnapshot::AddRootEntry() {

  ASSERT(root_index_ == HeapEntry::kNoEntry);

  ASSERT(entries_.is_empty());  // Root entry must be the first one.

  HeapEntry* entry = AddEntry(HeapEntry::kSynthetic,

                              "",

                              HeapObjectsMap::kInternalRootObjectId,

                              0);

  root_index_ = entry->index();

  ASSERT(root_index_ == 0);

  return entry;

}

HeapEntry* HeapSnapshot::AddGcRootsEntry() {

  ASSERT(gc_roots_index_ == HeapEntry::kNoEntry);

  HeapEntry* entry = AddEntry(HeapEntry::kSynthetic,

                              "(GC roots)",

                              HeapObjectsMap::kGcRootsObjectId,

                              0);

  gc_roots_index_ = entry->index();

  return entry;

}

HeapEntry* HeapSnapshot::AddGcSubrootEntry(int tag) {

  ASSERT(gc_subroot_indexes_[tag] == HeapEntry::kNoEntry);

  ASSERT(0 <= tag && tag < VisitorSynchronization::kNumberOfSyncTags);

  HeapEntry* entry = AddEntry(

      HeapEntry::kSynthetic,

      VisitorSynchronization::kTagNames[tag],

      HeapObjectsMap::GetNthGcSubrootId(tag),

      0);

  gc_subroot_indexes_[tag] = entry->index();

  return entry;

}

HeapEntry* HeapSnapshot::AddEntry(HeapEntry::Type type,

                                  const char* name,

                                  SnapshotObjectId id,

                                  int size) {

  HeapEntry entry(this, type, name, id, size);

  entries_.Add(entry);

  return &entries_.last();

}

void HeapSnapshot::FillChildren() {

  ASSERT(children().is_empty());

  children().Allocate(edges().length());

  int children_index = 0;

  for (int i = 0; i < entries().length(); ++i) {

    HeapEntry* entry = &entries()[i];

    children_index = entry->set_children_index(children_index);

  }

  ASSERT(edges().length() == children_index);

  for (int i = 0; i < edges().length(); ++i) {

    HeapGraphEdge* edge = &edges()[i];

    edge->ReplaceToIndexWithEntry(this);

    edge->from()->add_child(edge);

  }

}

class FindEntryById {

 public:

  explicit FindEntryById(SnapshotObjectId id) : id_(id) { }

  int operator()(HeapEntry* const* entry) {

    if ((*entry)->id() == id_) return 0;

    return (*entry)->id() < id_ ? -1 : 1;

  }

 private:

  SnapshotObjectId id_;

};

HeapEntry* HeapSnapshot::GetEntryById(SnapshotObjectId id) {

  List<HeapEntry*>* entries_by_id = GetSortedEntriesList();

  // Perform a binary search by id.

  int index = SortedListBSearch(*entries_by_id, FindEntryById(id));

  if (index == -1)

    return NULL;

  return entries_by_id->at(index);

}

template<class T>

static int SortByIds(const T* entry1_ptr,

                     const T* entry2_ptr) {

  if ((*entry1_ptr)->id() == (*entry2_ptr)->id()) return 0;

  return (*entry1_ptr)->id() < (*entry2_ptr)->id() ? -1 : 1;

}

List<HeapEntry*>* HeapSnapshot::GetSortedEntriesList() {

  if (sorted_entries_.is_empty()) {

    sorted_entries_.Allocate(entries_.length());

    for (int i = 0; i < entries_.length(); ++i) {

      sorted_entries_[i] = &entries_[i];

    }

    sorted_entries_.Sort(SortByIds);

  }

  return &sorted_entries_;

}

void HeapSnapshot::Print(int max_depth) {

  root()->Print("", "", max_depth, 0);

}

template<typename T, class P>

static size_t GetMemoryUsedByList(const List<T, P>& list) {

  return list.length() * sizeof(T) + sizeof(list);

}

size_t HeapSnapshot::RawSnapshotSize() const {

  return

      sizeof(*this) +

      GetMemoryUsedByList(entries_) +

      GetMemoryUsedByList(edges_) +

      GetMemoryUsedByList(children_) +

      GetMemoryUsedByList(sorted_entries_);

}

// We split IDs on evens for embedder objects (see

// HeapObjectsMap::GenerateId) and odds for native objects.

const SnapshotObjectId HeapObjectsMap::kInternalRootObjectId = 1;

const SnapshotObjectId HeapObjectsMap::kGcRootsObjectId =

    HeapObjectsMap::kInternalRootObjectId + HeapObjectsMap::kObjectIdStep;

const SnapshotObjectId HeapObjectsMap::kGcRootsFirstSubrootId =

    HeapObjectsMap::kGcRootsObjectId + HeapObjectsMap::kObjectIdStep;

const SnapshotObjectId HeapObjectsMap::kFirstAvailableObjectId =

    HeapObjectsMap::kGcRootsFirstSubrootId +

    VisitorSynchronization::kNumberOfSyncTags * HeapObjectsMap::kObjectIdStep;

static bool AddressesMatch(void* key1, void* key2) {

  return key1 == key2;

}

HeapObjectsMap::HeapObjectsMap(Heap* heap)

    : next_id_(kFirstAvailableObjectId),

      entries_map_(AddressesMatch),

      heap_(heap) {

  // This dummy element solves a problem with entries_map_.

  // When we do lookup in HashMap we see no difference between two cases:

  // it has an entry with NULL as the value or it has created

  // a new entry on the fly with NULL as the default value.

  // With such dummy element we have a guaranty that all entries_map_ entries

  // will have the value field grater than 0.

  // This fact is using in MoveObject method.

  entries_.Add(EntryInfo(0, NULL, 0));

}

void HeapObjectsMap::SnapshotGenerationFinished() {

  RemoveDeadEntries();

}

void HeapObjectsMap::MoveObject(Address from, Address to, int object_size) {

  ASSERT(to != NULL);

  ASSERT(from != NULL);

  if (from == to) return;

  void* from_value = entries_map_.Remove(from, ComputePointerHash(from));

  if (from_value == NULL) {

    // It may occur that some untracked object moves to an address X and there

    // is a tracked object at that address. In this case we should remove the

    // entry as we know that the object has died.

    void* to_value = entries_map_.Remove(to, ComputePointerHash(to));

    if (to_value != NULL) {

      int to_entry_info_index =

          static_cast<int>(reinterpret_cast<intptr_t>(to_value));

      entries_.at(to_entry_info_index).addr = NULL;

    }

  } else {

    HashMap::Entry* to_entry = entries_map_.Lookup(to, ComputePointerHash(to),

                                                   true);

    if (to_entry->value != NULL) {

      // We found the existing entry with to address for an old object.

      // Without this operation we will have two EntryInfo's with the same

      // value in addr field. It is bad because later at RemoveDeadEntries

      // one of this entry will be removed with the corresponding entries_map_

      // entry.

      int to_entry_info_index =

          static_cast<int>(reinterpret_cast<intptr_t>(to_entry->value));

      entries_.at(to_entry_info_index).addr = NULL;

    }

    int from_entry_info_index =

        static_cast<int>(reinterpret_cast<intptr_t>(from_value));

    entries_.at(from_entry_info_index).addr = to;

    // Size of an object can change during its life, so to keep information

    // about the object in entries_ consistent, we have to adjust size when the

    // object is migrated.

    if (FLAG_heap_profiler_trace_objects) {

      PrintF("Move object from %p to %p old size %6d new size %6d\n",

             from,

             to,

             entries_.at(from_entry_info_index).size,

             object_size);

    }

    entries_.at(from_entry_info_index).size = object_size;

    to_entry->value = from_value;

  }

}

void HeapObjectsMap::NewObject(Address addr, int size) {

  if (FLAG_heap_profiler_trace_objects) {

    PrintF("New object         : %p %6d. Next address is %p\n",

           addr,

           size,

           addr + size);

  }

  ASSERT(addr != NULL);

  FindOrAddEntry(addr, size, false);

}

void HeapObjectsMap::UpdateObjectSize(Address addr, int size) {

  FindOrAddEntry(addr, size, false);

}

SnapshotObjectId HeapObjectsMap::FindEntry(Address addr) {

  HashMap::Entry* entry = entries_map_.Lookup(addr, ComputePointerHash(addr),

                                              false);

  if (entry == NULL) return 0;

  int entry_index = static_cast<int>(reinterpret_cast<intptr_t>(entry->value));

  EntryInfo& entry_info = entries_.at(entry_index);

  ASSERT(static_cast<uint32_t>(entries_.length()) > entries_map_.occupancy());

  return entry_info.id;

}

SnapshotObjectId HeapObjectsMap::FindOrAddEntry(Address addr,

                                                unsigned int size,

                                                bool accessed) {

  ASSERT(static_cast<uint32_t>(entries_.length()) > entries_map_.occupancy());

  HashMap::Entry* entry = entries_map_.Lookup(addr, ComputePointerHash(addr),

                                              true);

  if (entry->value != NULL) {

    int entry_index =

        static_cast<int>(reinterpret_cast<intptr_t>(entry->value));

    EntryInfo& entry_info = entries_.at(entry_index);

    entry_info.accessed = accessed;

    if (FLAG_heap_profiler_trace_objects) {

      PrintF("Update object size : %p with old size %d and new size %d\n",

             addr,

             entry_info.size,

             size);

    }

    entry_info.size = size;

    return entry_info.id;

  }

  entry->value = reinterpret_cast<void*>(entries_.length());

  SnapshotObjectId id = next_id_;

  next_id_ += kObjectIdStep;

  entries_.Add(EntryInfo(id, addr, size, accessed));

  ASSERT(static_cast<uint32_t>(entries_.length()) > entries_map_.occupancy());

  return id;

}

void HeapObjectsMap::StopHeapObjectsTracking() {

  time_intervals_.Clear();

}

void HeapObjectsMap::UpdateHeapObjectsMap() {

  if (FLAG_heap_profiler_trace_objects) {

    PrintF("Begin HeapObjectsMap::UpdateHeapObjectsMap. map has %d entries.\n",

           entries_map_.occupancy());

  }

  heap_->CollectAllGarbage(Heap::kMakeHeapIterableMask,

                          "HeapSnapshotsCollection::UpdateHeapObjectsMap");

  HeapIterator iterator(heap_);

  for (HeapObject* obj = iterator.next();

       obj != NULL;

       obj = iterator.next()) {

    FindOrAddEntry(obj->address(), obj->Size());

    if (FLAG_heap_profiler_trace_objects) {

      PrintF("Update object      : %p %6d. Next address is %p\n",

             obj->address(),

             obj->Size(),

             obj->address() + obj->Size());

    }

  }

  RemoveDeadEntries();

  if (FLAG_heap_profiler_trace_objects) {

    PrintF("End HeapObjectsMap::UpdateHeapObjectsMap. map has %d entries.\n",

           entries_map_.occupancy());

  }

}

namespace {

struct HeapObjectInfo {

  HeapObjectInfo(HeapObject* obj, int expected_size)

    : obj(obj),

      expected_size(expected_size) {

  }

  HeapObject* obj;

  int expected_size;

  bool IsValid() const { return expected_size == obj->Size(); }

  void Print() const {

    if (expected_size == 0) {

      PrintF("Untracked object   : %p %6d. Next address is %p\n",

             obj->address(),

             obj->Size(),

             obj->address() + obj->Size());

    } else if (obj->Size() != expected_size) {

      PrintF("Wrong size %6d: %p %6d. Next address is %p\n",

             expected_size,

             obj->address(),

             obj->Size(),

             obj->address() + obj->Size());

    } else {

      PrintF("Good object      : %p %6d. Next address is %p\n",

             obj->address(),

             expected_size,

             obj->address() + obj->Size());

    }

  }

};

static int comparator(const HeapObjectInfo* a, const HeapObjectInfo* b) {

  if (a->obj < b->obj) return -1;

  if (a->obj > b->obj) return 1;

  return 0;

}

}  // namespace

int HeapObjectsMap::FindUntrackedObjects() {

  List<HeapObjectInfo> heap_objects(1000);

  HeapIterator iterator(heap_);

  int untracked = 0;

  for (HeapObject* obj = iterator.next();

       obj != NULL;

       obj = iterator.next()) {

    HashMap::Entry* entry = entries_map_.Lookup(

      obj->address(), ComputePointerHash(obj->address()), false);

    if (entry == NULL) {

      ++untracked;

      if (FLAG_heap_profiler_trace_objects) {

        heap_objects.Add(HeapObjectInfo(obj, 0));

      }

    } else {

      int entry_index = static_cast<int>(

          reinterpret_cast<intptr_t>(entry->value));

      EntryInfo& entry_info = entries_.at(entry_index);

      if (FLAG_heap_profiler_trace_objects) {

        heap_objects.Add(HeapObjectInfo(obj,

                         static_cast<int>(entry_info.size)));

        if (obj->Size() != static_cast<int>(entry_info.size))

          ++untracked;

      } else {

        CHECK_EQ(obj->Size(), static_cast<int>(entry_info.size));

      }

    }

  }

  if (FLAG_heap_profiler_trace_objects) {

    PrintF("\nBegin HeapObjectsMap::FindUntrackedObjects. %d entries in map.\n",

           entries_map_.occupancy());

    heap_objects.Sort(comparator);

    int last_printed_object = -1;

    bool print_next_object = false;

    for (int i = 0; i < heap_objects.length(); ++i) {

      const HeapObjectInfo& object_info = heap_objects[i];

      if (!object_info.IsValid()) {

        ++untracked;

        if (last_printed_object != i - 1) {

          if (i > 0) {

            PrintF("%d objects were skipped\n", i - 1 - last_printed_object);

            heap_objects[i - 1].Print();

          }

        }

        object_info.Print();

        last_printed_object = i;

        print_next_object = true;

      } else if (print_next_object) {

        object_info.Print();

        print_next_object = false;

        last_printed_object = i;

      }

    }

    if (last_printed_object < heap_objects.length() - 1) {

      PrintF("Last %d objects were skipped\n",

             heap_objects.length() - 1 - last_printed_object);

    }

    PrintF("End HeapObjectsMap::FindUntrackedObjects. %d entries in map.\n\n",

           entries_map_.occupancy());

  }

  return untracked;

}

SnapshotObjectId HeapObjectsMap::PushHeapObjectsStats(OutputStream* stream) {

  UpdateHeapObjectsMap();

  time_intervals_.Add(TimeInterval(next_id_));

  int prefered_chunk_size = stream->GetChunkSize();

  List<v8::HeapStatsUpdate> stats_buffer;

  ASSERT(!entries_.is_empty());

  EntryInfo* entry_info = &entries_.first();

  EntryInfo* end_entry_info = &entries_.last() + 1;

  for (int time_interval_index = 0;

       time_interval_index < time_intervals_.length();

       ++time_interval_index) {

    TimeInterval& time_interval = time_intervals_[time_interval_index];

    SnapshotObjectId time_interval_id = time_interval.id;

    uint32_t entries_size = 0;

    EntryInfo* start_entry_info = entry_info;

    while (entry_info < end_entry_info && entry_info->id < time_interval_id) {

      entries_size += entry_info->size;

      ++entry_info;

    }

    uint32_t entries_count =

        static_cast<uint32_t>(entry_info - start_entry_info);

    if (time_interval.count != entries_count ||

        time_interval.size != entries_size) {

      stats_buffer.Add(v8::HeapStatsUpdate(

          time_interval_index,

          time_interval.count = entries_count,

          time_interval.size = entries_size));

      if (stats_buffer.length() >= prefered_chunk_size) {

        OutputStream::WriteResult result = stream->WriteHeapStatsChunk(

            &stats_buffer.first(), stats_buffer.length());

        if (result == OutputStream::kAbort) return last_assigned_id();

        stats_buffer.Clear();

      }

    }

  }

  ASSERT(entry_info == end_entry_info);

  if (!stats_buffer.is_empty()) {

    OutputStream::WriteResult result = stream->WriteHeapStatsChunk(

        &stats_buffer.first(), stats_buffer.length());

    if (result == OutputStream::kAbort) return last_assigned_id();

  }

  stream->EndOfStream();

  return last_assigned_id();

}

void HeapObjectsMap::RemoveDeadEntries() {

  ASSERT(entries_.length() > 0 &&

         entries_.at(0).id == 0 &&

         entries_.at(0).addr == NULL);

  int first_free_entry = 1;

  for (int i = 1; i < entries_.length(); ++i) {

    EntryInfo& entry_info = entries_.at(i);

    if (entry_info.accessed) {

      if (first_free_entry != i) {

        entries_.at(first_free_entry) = entry_info;

      }

      entries_.at(first_free_entry).accessed = false;

      HashMap::Entry* entry = entries_map_.Lookup(

          entry_info.addr, ComputePointerHash(entry_info.addr), false);

      ASSERT(entry);

      entry->value = reinterpret_cast<void*>(first_free_entry);

      ++first_free_entry;

    } else {

      if (entry_info.addr) {

        entries_map_.Remove(entry_info.addr,

                            ComputePointerHash(entry_info.addr));

      }

    }

  }

  entries_.Rewind(first_free_entry);

  ASSERT(static_cast<uint32_t>(entries_.length()) - 1 ==

         entries_map_.occupancy());

}

SnapshotObjectId HeapObjectsMap::GenerateId(Heap* heap,

                                            v8::RetainedObjectInfo* info) {

  SnapshotObjectId id = static_cast<SnapshotObjectId>(info->GetHash());

  const char* label = info->GetLabel();

  id ^= StringHasher::HashSequentialString(label,

                                           static_cast<int>(strlen(label)),

                                           heap->HashSeed());

  intptr_t element_count = info->GetElementCount();

  if (element_count != -1)

    id ^= ComputeIntegerHash(static_cast<uint32_t>(element_count),

                             v8::internal::kZeroHashSeed);

  return id << 1;

}

size_t HeapObjectsMap::GetUsedMemorySize() const {

  return

      sizeof(*this) +

      sizeof(HashMap::Entry) * entries_map_.capacity() +

      GetMemoryUsedByList(entries_) +

      GetMemoryUsedByList(time_intervals_);

}

HeapSnapshotsCollection::HeapSnapshotsCollection(Heap* heap)

    : is_tracking_objects_(false),

      names_(heap),

      ids_(heap),

      allocation_tracker_(NULL) {

}

static void DeleteHeapSnapshot(HeapSnapshot** snapshot_ptr) {

  delete *snapshot_ptr;

}

HeapSnapshotsCollection::~HeapSnapshotsCollection() {

  delete allocation_tracker_;

  snapshots_.Iterate(DeleteHeapSnapshot);

}

void HeapSnapshotsCollection::StartHeapObjectsTracking() {

  ids_.UpdateHeapObjectsMap();

  if (allocation_tracker_ == NULL) {

    allocation_tracker_ = new AllocationTracker(&ids_, names());

  }

  is_tracking_objects_ = true;

}

void HeapSnapshotsCollection::StopHeapObjectsTracking() {

  ids_.StopHeapObjectsTracking();

  if (allocation_tracker_ != NULL) {

    delete allocation_tracker_;

    allocation_tracker_ = NULL;

  }

}

HeapSnapshot* HeapSnapshotsCollection::NewSnapshot(const char* name,

                                                   unsigned uid) {

  is_tracking_objects_ = true;  // Start watching for heap objects moves.

  return new HeapSnapshot(this, name, uid);

}

void HeapSnapshotsCollection::SnapshotGenerationFinished(

    HeapSnapshot* snapshot) {

  ids_.SnapshotGenerationFinished();

  if (snapshot != NULL) {

    snapshots_.Add(snapshot);

  }

}

void HeapSnapshotsCollection::RemoveSnapshot(HeapSnapshot* snapshot) {

  snapshots_.RemoveElement(snapshot);

}

Handle<HeapObject> HeapSnapshotsCollection::FindHeapObjectById(

    SnapshotObjectId id) {

  // First perform a full GC in order to avoid dead objects.

  heap()->CollectAllGarbage(Heap::kMakeHeapIterableMask,

                          "HeapSnapshotsCollection::FindHeapObjectById");

  DisallowHeapAllocation no_allocation;

  HeapObject* object = NULL;

  HeapIterator iterator(heap(), HeapIterator::kFilterUnreachable);

  // Make sure that object with the given id is still reachable.

  for (HeapObject* obj = iterator.next();

       obj != NULL;

       obj = iterator.next()) {

    if (ids_.FindEntry(obj->address()) == id) {

      ASSERT(object == NULL);

      object = obj;

      // Can't break -- kFilterUnreachable requires full heap traversal.

    }

  }

  return object != NULL ? Handle<HeapObject>(object) : Handle<HeapObject>();

}

void HeapSnapshotsCollection::NewObjectEvent(Address addr, int size) {

  DisallowHeapAllocation no_allocation;

  ids_.NewObject(addr, size);

  if (allocation_tracker_ != NULL) {

    allocation_tracker_->NewObjectEvent(addr, size);

  }

}

size_t HeapSnapshotsCollection::GetUsedMemorySize() const {

  size_t size = sizeof(*this);

  size += names_.GetUsedMemorySize();

  size += ids_.GetUsedMemorySize();

  size += GetMemoryUsedByList(snapshots_);

  for (int i = 0; i < snapshots_.length(); ++i) {

    size += snapshots_[i]->RawSnapshotSize();

  }

  return size;

}

HeapEntriesMap::HeapEntriesMap()

    : entries_(HeapThingsMatch) {

}

int HeapEntriesMap::Map(HeapThing thing) {

  HashMap::Entry* cache_entry = entries_.Lookup(thing, Hash(thing), false);

  if (cache_entry == NULL) return HeapEntry::kNoEntry;

  return static_cast<int>(reinterpret_cast<intptr_t>(cache_entry->value));

}

void HeapEntriesMap::Pair(HeapThing thing, int entry) {

  HashMap::Entry* cache_entry = entries_.Lookup(thing, Hash(thing), true);

  ASSERT(cache_entry->value == NULL);

  cache_entry->value = reinterpret_cast<void*>(static_cast<intptr_t>(entry));

}

HeapObjectsSet::HeapObjectsSet()

    : entries_(HeapEntriesMap::HeapThingsMatch) {

}

void HeapObjectsSet::Clear() {

  entries_.Clear();

}

bool HeapObjectsSet::Contains(Object* obj) {

  if (!obj->IsHeapObject()) return false;

  HeapObject* object = HeapObject::cast(obj);

  return entries_.Lookup(object, HeapEntriesMap::Hash(object), false) != NULL;

}

void HeapObjectsSet::Insert(Object* obj) {

  if (!obj->IsHeapObject()) return;

  HeapObject* object = HeapObject::cast(obj);

  entries_.Lookup(object, HeapEntriesMap::Hash(object), true);

}

const char* HeapObjectsSet::GetTag(Object* obj) {

  HeapObject* object = HeapObject::cast(obj);

  HashMap::Entry* cache_entry =

      entries_.Lookup(object, HeapEntriesMap::Hash(object), false);

  return cache_entry != NULL

      ? reinterpret_cast<const char*>(cache_entry->value)

      : NULL;

}

void HeapObjectsSet::SetTag(Object* obj, const char* tag) {

  if (!obj->IsHeapObject()) return;

  HeapObject* object = HeapObject::cast(obj);

  HashMap::Entry* cache_entry =

      entries_.Lookup(object, HeapEntriesMap::Hash(object), true);

  cache_entry->value = const_cast<char*>(tag);

}

HeapObject* const V8HeapExplorer::kInternalRootObject =

    reinterpret_cast<HeapObject*>(

        static_cast<intptr_t>(HeapObjectsMap::kInternalRootObjectId));

HeapObject* const V8HeapExplorer::kGcRootsObject =

    reinterpret_cast<HeapObject*>(

        static_cast<intptr_t>(HeapObjectsMap::kGcRootsObjectId));

HeapObject* const V8HeapExplorer::kFirstGcSubrootObject =

    reinterpret_cast<HeapObject*>(

        static_cast<intptr_t>(HeapObjectsMap::kGcRootsFirstSubrootId));

HeapObject* const V8HeapExplorer::kLastGcSubrootObject =

    reinterpret_cast<HeapObject*>(

        static_cast<intptr_t>(HeapObjectsMap::kFirstAvailableObjectId));

V8HeapExplorer::V8HeapExplorer(

    HeapSnapshot* snapshot,

    SnapshottingProgressReportingInterface* progress,

    v8::HeapProfiler::ObjectNameResolver* resolver)

    : heap_(snapshot->collection()->heap()),

      snapshot_(snapshot),

      collection_(snapshot_->collection()),

      progress_(progress),

      filler_(NULL),

      global_object_name_resolver_(resolver) {

}

V8HeapExplorer::~V8HeapExplorer() {

}

HeapEntry* V8HeapExplorer::AllocateEntry(HeapThing ptr) {

  return AddEntry(reinterpret_cast<HeapObject*>(ptr));

}

HeapEntry* V8HeapExplorer::AddEntry(HeapObject* object) {

  if (object == kInternalRootObject) {

    snapshot_->AddRootEntry();

    return snapshot_->root();

  } else if (object == kGcRootsObject) {

    HeapEntry* entry = snapshot_->AddGcRootsEntry();

    return entry;

  } else if (object >= kFirstGcSubrootObject && object < kLastGcSubrootObject) {

    HeapEntry* entry = snapshot_->AddGcSubrootEntry(GetGcSubrootOrder(object));

    return entry;

  } else if (object->IsJSFunction()) {

    JSFunction* func = JSFunction::cast(object);

    SharedFunctionInfo* shared = func->shared();

    const char* name = shared->bound() ? "native_bind" :

        collection_->names()->GetName(String::cast(shared->name()));

    return AddEntry(object, HeapEntry::kClosure, name);

  } else if (object->IsJSRegExp()) {

    JSRegExp* re = JSRegExp::cast(object);

    return AddEntry(object,

                    HeapEntry::kRegExp,

                    collection_->names()->GetName(re->Pattern()));

  } else if (object->IsJSObject()) {

    const char* name = collection_->names()->GetName(

        GetConstructorName(JSObject::cast(object)));

    if (object->IsJSGlobalObject()) {

      const char* tag = objects_tags_.GetTag(object);

      if (tag != NULL) {

        name = collection_->names()->GetFormatted("%s / %s", name, tag);

      }

    }

    return AddEntry(object, HeapEntry::kObject, name);

  } else if (object->IsString()) {

    String* string = String::cast(object);

    if (string->IsConsString())

      return AddEntry(object,

                      HeapEntry::kConsString,

                      "(concatenated string)");

    if (string->IsSlicedString())

      return AddEntry(object,

                      HeapEntry::kSlicedString,

                      "(sliced string)");

    return AddEntry(object,

                    HeapEntry::kString,

                    collection_->names()->GetName(String::cast(object)));

  } else if (object->IsCode()) {

    return AddEntry(object, HeapEntry::kCode, "");

  } else if (object->IsSharedFunctionInfo()) {

    String* name = String::cast(SharedFunctionInfo::cast(object)->name());

    return AddEntry(object,

                    HeapEntry::kCode,

                    collection_->names()->GetName(name));

  } else if (object->IsScript()) {

    Object* name = Script::cast(object)->name();

    return AddEntry(object,

                    HeapEntry::kCode,

                    name->IsString()

                        ? collection_->names()->GetName(String::cast(name))

                        : "");

  } else if (object->IsNativeContext()) {

    return AddEntry(object, HeapEntry::kHidden, "system / NativeContext");

  } else if (object->IsContext()) {

    return AddEntry(object, HeapEntry::kObject, "system / Context");

  } else if (object->IsFixedArray() ||

             object->IsFixedDoubleArray() ||

             object->IsByteArray() ||

             object->IsExternalArray()) {

    return AddEntry(object, HeapEntry::kArray, "");

  } else if (object->IsHeapNumber()) {

    return AddEntry(object, HeapEntry::kHeapNumber, "number");

  }

  return AddEntry(object, HeapEntry::kHidden, GetSystemEntryName(object));

}

HeapEntry* V8HeapExplorer::AddEntry(HeapObject* object,

                                    HeapEntry::Type type,

                                    const char* name) {

  int object_size = object->Size();

  SnapshotObjectId object_id =

    collection_->GetObjectId(object->address(), object_size);

  return snapshot_->AddEntry(type, name, object_id, object_size);

}

class GcSubrootsEnumerator : public ObjectVisitor {

 public:

  GcSubrootsEnumerator(

      SnapshotFillerInterface* filler, V8HeapExplorer* explorer)

      : filler_(filler),

        explorer_(explorer),

        previous_object_count_(0),

        object_count_(0) {

  }

  void VisitPointers(Object** start, Object** end) {

    object_count_ += end - start;

  }

  void Synchronize(VisitorSynchronization::SyncTag tag) {

    // Skip empty subroots.

    if (previous_object_count_ != object_count_) {

      previous_object_count_ = object_count_;

      filler_->AddEntry(V8HeapExplorer::GetNthGcSubrootObject(tag), explorer_);

    }

  }

 private:

  SnapshotFillerInterface* filler_;

  V8HeapExplorer* explorer_;

  intptr_t previous_object_count_;

  intptr_t object_count_;

};

void V8HeapExplorer::AddRootEntries(SnapshotFillerInterface* filler) {

  filler->AddEntry(kInternalRootObject, this);

  filler->AddEntry(kGcRootsObject, this);

  GcSubrootsEnumerator enumerator(filler, this);

  heap_->IterateRoots(&enumerator, VISIT_ALL);

}

const char* V8HeapExplorer::GetSystemEntryName(HeapObject* object) {

  switch (object->map()->instance_type()) {

    case MAP_TYPE:

      switch (Map::cast(object)->instance_type()) {

#define MAKE_STRING_MAP_CASE(instance_type, size, name, Name) \

        case instance_type: return "system / Map (" #Name ")";

      STRING_TYPE_LIST(MAKE_STRING_MAP_CASE)

#undef MAKE_STRING_MAP_CASE

        default: return "system / Map";

      }

    case CELL_TYPE: return "system / Cell";

    case PROPERTY_CELL_TYPE: return "system / PropertyCell";

    case FOREIGN_TYPE: return "system / Foreign";

    case ODDBALL_TYPE: return "system / Oddball";

#define MAKE_STRUCT_CASE(NAME, Name, name) \

    case NAME##_TYPE: return "system / "#Name;

  STRUCT_LIST(MAKE_STRUCT_CASE)

#undef MAKE_STRUCT_CASE

    default: return "system";

  }

}

int V8HeapExplorer::EstimateObjectsCount(HeapIterator* iterator) {

  int objects_count = 0;

  for (HeapObject* obj = iterator->next();

       obj != NULL;

       obj = iterator->next()) {

    objects_count++;

  }

  return objects_count;

}

class IndexedReferencesExtractor : public ObjectVisitor {

 public:

  IndexedReferencesExtractor(V8HeapExplorer* generator,

                             HeapObject* parent_obj,

                             int parent)

      : generator_(generator),

        parent_obj_(parent_obj),

        parent_(parent),

        next_index_(0) {

  }

  void VisitCodeEntry(Address entry_address) {

     Code* code = Code::cast(Code::GetObjectFromEntryAddress(entry_address));

     generator_->SetInternalReference(parent_obj_, parent_, "code", code);

     generator_->TagObject(code, "(code)");

  }

  void VisitPointers(Object** start, Object** end) {

    for (Object** p = start; p < end; p++) {

      if (CheckVisitedAndUnmark(p)) continue;

      generator_->SetHiddenReference(parent_obj_, parent_, next_index_++, *p);

    }

  }

  static void MarkVisitedField(HeapObject* obj, int offset) {

    if (offset < 0) return;

    Address field = obj->address() + offset;

    ASSERT(!Memory::Object_at(field)->IsFailure());

    ASSERT(Memory::Object_at(field)->IsHeapObject());

    *field |= kFailureTag;

  }

 private:

  bool CheckVisitedAndUnmark(Object** field) {

    if ((*field)->IsFailure()) {

      intptr_t untagged = reinterpret_cast<intptr_t>(*field) & ~kFailureTagMask;

      *field = reinterpret_cast<Object*>(untagged | kHeapObjectTag);

      ASSERT((*field)->IsHeapObject());

      return true;

    }

    return false;

  }

  V8HeapExplorer* generator_;

  HeapObject* parent_obj_;

  int parent_;

  int next_index_;

};

void V8HeapExplorer::ExtractReferences(HeapObject* obj) {

  HeapEntry* heap_entry = GetEntry(obj);

  if (heap_entry == NULL) return;  // No interest in this object.

  int entry = heap_entry->index();

  if (obj->IsJSGlobalProxy()) {

    ExtractJSGlobalProxyReferences(entry, JSGlobalProxy::cast(obj));

  } else if (obj->IsJSObject()) {

    ExtractJSObjectReferences(entry, JSObject::cast(obj));

  } else if (obj->IsString()) {

    ExtractStringReferences(entry, String::cast(obj));

  } else if (obj->IsContext()) {

    ExtractContextReferences(entry, Context::cast(obj));

  } else if (obj->IsMap()) {

    ExtractMapReferences(entry, Map::cast(obj));

  } else if (obj->IsSharedFunctionInfo()) {

    ExtractSharedFunctionInfoReferences(entry, SharedFunctionInfo::cast(obj));

  } else if (obj->IsScript()) {

    ExtractScriptReferences(entry, Script::cast(obj));

  } else if (obj->IsAccessorPair()) {

    ExtractAccessorPairReferences(entry, AccessorPair::cast(obj));

  } else if (obj->IsCodeCache()) {

    ExtractCodeCacheReferences(entry, CodeCache::cast(obj));

  } else if (obj->IsCode()) {

    ExtractCodeReferences(entry, Code::cast(obj));

  } else if (obj->IsCell()) {

    ExtractCellReferences(entry, Cell::cast(obj));

  } else if (obj->IsPropertyCell()) {

    ExtractPropertyCellReferences(entry, PropertyCell::cast(obj));

  } else if (obj->IsAllocationSite()) {

    ExtractAllocationSiteReferences(entry, AllocationSite::cast(obj));

  }

  SetInternalReference(obj, entry, "map", obj->map(), HeapObject::kMapOffset);

  // Extract unvisited fields as hidden references and restore tags

  // of visited fields.

  IndexedReferencesExtractor refs_extractor(this, obj, entry);

  obj->Iterate(&refs_extractor);

}

void V8HeapExplorer::ExtractJSGlobalProxyReferences(

    int entry, JSGlobalProxy* proxy) {

  SetInternalReference(proxy, entry,

                       "native_context", proxy->native_context(),

                       JSGlobalProxy::kNativeContextOffset);

}

void V8HeapExplorer::ExtractJSObjectReferences(

    int entry, JSObject* js_obj) {

  HeapObject* obj = js_obj;

  ExtractClosureReferences(js_obj, entry);

  ExtractPropertyReferences(js_obj, entry);

  ExtractElementReferences(js_obj, entry);

  ExtractInternalReferences(js_obj, entry);

  SetPropertyReference(

      obj, entry, heap_->proto_string(), js_obj->GetPrototype());

  if (obj->IsJSFunction()) {

    JSFunction* js_fun = JSFunction::cast(js_obj);

    Object* proto_or_map = js_fun->prototype_or_initial_map();

    if (!proto_or_map->IsTheHole()) {

      if (!proto_or_map->IsMap()) {

        SetPropertyReference(

            obj, entry,

            heap_->prototype_string(), proto_or_map,

            NULL,

            JSFunction::kPrototypeOrInitialMapOffset);

      } else {

        SetPropertyReference(

            obj, entry,

            heap_->prototype_string(), js_fun->prototype());

        SetInternalReference(

            obj, entry, "initial_map", proto_or_map,

            JSFunction::kPrototypeOrInitialMapOffset);

      }

    }

    SharedFunctionInfo* shared_info = js_fun->shared();

    // JSFunction has either bindings or literals and never both.

    bool bound = shared_info->bound();

    TagObject(js_fun->literals_or_bindings(),

              bound ? "(function bindings)" : "(function literals)");

    SetInternalReference(js_fun, entry,

                         bound ? "bindings" : "literals",

                         js_fun->literals_or_bindings(),

                         JSFunction::kLiteralsOffset);

    TagObject(shared_info, "(shared function info)");

    SetInternalReference(js_fun, entry,

                         "shared", shared_info,

                         JSFunction::kSharedFunctionInfoOffset);

    TagObject(js_fun->context(), "(context)");

    SetInternalReference(js_fun, entry,

                         "context", js_fun->context(),

                         JSFunction::kContextOffset);

    for (int i = JSFunction::kNonWeakFieldsEndOffset;

         i < JSFunction::kSize;

         i += kPointerSize) {

      SetWeakReference(js_fun, entry, i, *HeapObject::RawField(js_fun, i), i);

    }

  } else if (obj->IsGlobalObject()) {

    GlobalObject* global_obj = GlobalObject::cast(obj);

    SetInternalReference(global_obj, entry,

                         "builtins", global_obj->builtins(),

                         GlobalObject::kBuiltinsOffset);

    SetInternalReference(global_obj, entry,

                         "native_context", global_obj->native_context(),

                         GlobalObject::kNativeContextOffset);

    SetInternalReference(global_obj, entry,

                         "global_receiver", global_obj->global_receiver(),

                         GlobalObject::kGlobalReceiverOffset);

  }

  TagObject(js_obj->properties(), "(object properties)");

  SetInternalReference(obj, entry,

                       "properties", js_obj->properties(),

                       JSObject::kPropertiesOffset);

  TagObject(js_obj->elements(), "(object elements)");

  SetInternalReference(obj, entry,

                       "elements", js_obj->elements(),

                       JSObject::kElementsOffset);

}

void V8HeapExplorer::ExtractStringReferences(int entry, String* string) {

  if (string->IsConsString()) {

    ConsString* cs = ConsString::cast(string);

    SetInternalReference(cs, entry, "first", cs->first(),

                         ConsString::kFirstOffset);

    SetInternalReference(cs, entry, "second", cs->second(),

                         ConsString::kSecondOffset);

  } else if (string->IsSlicedString()) {

    SlicedString* ss = SlicedString::cast(string);

    SetInternalReference(ss, entry, "parent", ss->parent(),

                         SlicedString::kParentOffset);

  }

}

void V8HeapExplorer::ExtractContextReferences(int entry, Context* context) {

  if (context == context->declaration_context()) {

    ScopeInfo* scope_info = context->closure()->shared()->scope_info();

    // Add context allocated locals.

    int context_locals = scope_info->ContextLocalCount();

    for (int i = 0; i < context_locals; ++i) {

      String* local_name = scope_info->ContextLocalName(i);

      int idx = Context::MIN_CONTEXT_SLOTS + i;

      SetContextReference(context, entry, local_name, context->get(idx),

                          Context::OffsetOfElementAt(idx));

    }

    if (scope_info->HasFunctionName()) {

      String* name = scope_info->FunctionName();

      VariableMode mode;

      int idx = scope_info->FunctionContextSlotIndex(name, &mode);

      if (idx >= 0) {

        SetContextReference(context, entry, name, context->get(idx),

                            Context::OffsetOfElementAt(idx));

      }

    }

  }

#define EXTRACT_CONTEXT_FIELD(index, type, name) \

  SetInternalReference(context, entry, #name, context->get(Context::index), \

      FixedArray::OffsetOfElementAt(Context::index));

  EXTRACT_CONTEXT_FIELD(CLOSURE_INDEX, JSFunction, closure);

  EXTRACT_CONTEXT_FIELD(PREVIOUS_INDEX, Context, previous);

  EXTRACT_CONTEXT_FIELD(EXTENSION_INDEX, Object, extension);

  EXTRACT_CONTEXT_FIELD(GLOBAL_OBJECT_INDEX, GlobalObject, global);

  if (context->IsNativeContext()) {

    TagObject(context->jsfunction_result_caches(),

              "(context func. result caches)");

    TagObject(context->normalized_map_cache(), "(context norm. map cache)");

    TagObject(context->runtime_context(), "(runtime context)");

    TagObject(context->embedder_data(), "(context data)");

    NATIVE_CONTEXT_FIELDS(EXTRACT_CONTEXT_FIELD);

#undef EXTRACT_CONTEXT_FIELD

    for (int i = Context::FIRST_WEAK_SLOT;

         i < Context::NATIVE_CONTEXT_SLOTS;

         ++i) {

      SetWeakReference(context, entry, i, context->get(i),

          FixedArray::OffsetOfElementAt(i));

    }

  }

}

void V8HeapExplorer::ExtractMapReferences(int entry, Map* map) {

  if (map->HasTransitionArray()) {

    TransitionArray* transitions = map->transitions();

    int transitions_entry = GetEntry(transitions)->index();

    Object* back_pointer = transitions->back_pointer_storage();

    TagObject(back_pointer, "(back pointer)");

    SetInternalReference(transitions, transitions_entry,

                         "back_pointer", back_pointer);

    TagObject(transitions, "(transition array)");