Revision: 11259
Author: [email protected]
Date: Tue Apr 10 23:58:42 2012
Log: I'd like to add addr field into EntryInfo struct.
This will give us the ability to keep entries_ list sorted by id.
And based on that fact we will be able to use it for:
1) GetNodeById method and drop sorted version of entries list in
HeapSnapshot;
2) building heap stats;
3) doing the fill stage instead of second iteration over heap.
BUG=none
TEST=none
R=yurys
Review URL: https://chromiumcodereview.appspot.com/10031032
http://code.google.com/p/v8/source/detail?r=11259
Modified:
/branches/bleeding_edge/src/hashmap.h
/branches/bleeding_edge/src/profile-generator.cc
/branches/bleeding_edge/src/profile-generator.h
=======================================
--- /branches/bleeding_edge/src/hashmap.h Thu Mar 15 08:01:59 2012
+++ /branches/bleeding_edge/src/hashmap.h Tue Apr 10 23:58:42 2012
@@ -63,7 +63,9 @@
Entry* Lookup(void* key, uint32_t hash, bool insert);
// Removes the entry with matching key.
- void Remove(void* key, uint32_t hash);
+ // It returns the value of the deleted entry
+ // or null if there is no value for such key.
+ void* Remove(void* key, uint32_t hash);
// Empties the hash map (occupancy() == 0).
void Clear();
@@ -146,14 +148,15 @@
template<class P>
-void TemplateHashMapImpl<P>::Remove(void* key, uint32_t hash) {
+void* TemplateHashMapImpl<P>::Remove(void* key, uint32_t hash) {
// Lookup the entry for the key to remove.
Entry* p = Probe(key, hash);
if (p->key == NULL) {
// Key not found nothing to remove.
- return;
+ return NULL;
}
+ void* value = p->value;
// To remove an entry we need to ensure that it does not create an empty
// entry that will cause the search for another entry to stop too soon.
If all
// the entries between the entry to remove and the next empty slot have
their
@@ -202,6 +205,7 @@
// Clear the entry which is allowed to en emptied.
p->key = NULL;
occupancy_--;
+ return value;
}
=======================================
--- /branches/bleeding_edge/src/profile-generator.cc Tue Apr 10 04:24:09
2012
+++ /branches/bleeding_edge/src/profile-generator.cc Tue Apr 10 23:58:42
2012
@@ -1315,7 +1315,16 @@
: initial_fill_mode_(true),
next_id_(kFirstAvailableObjectId),
entries_map_(AddressesMatch),
- entries_(new List<EntryInfo>()) { }
+ entries_(new List<EntryInfo>()) {
+ // 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));
+}
HeapObjectsMap::~HeapObjectsMap() {
@@ -1337,31 +1346,47 @@
SnapshotObjectId id = next_id_;
next_id_ += kObjectIdStep;
AddEntry(addr, id);
+ // Here and in other places the length of entries_ list has to be
+ // the same or greater than the length of entries_map_. But entries_ list
+ // has a dummy element at index 0.
+ ASSERT(static_cast<uint32_t>(entries_->length()) >
entries_map_.occupancy());
return id;
}
void HeapObjectsMap::MoveObject(Address from, Address to) {
+ ASSERT(to != NULL);
+ ASSERT(from != NULL);
if (from == to) return;
- HashMap::Entry* entry = entries_map_.Lookup(from, AddressHash(from),
false);
- if (entry != NULL) {
- void* value = entry->value;
- entries_map_.Remove(from, AddressHash(from));
- if (to != NULL) {
- entry = entries_map_.Lookup(to, AddressHash(to), true);
- // We can have an entry at the new location, it is OK, as GC can
overwrite
- // dead objects with alive objects being moved.
- entry->value = value;
- }
- }
+ void* from_value = entries_map_.Remove(from, AddressHash(from));
+ if (from_value == NULL) return;
+ int from_entry_info_index =
+ static_cast<int>(reinterpret_cast<intptr_t>(from_value));
+ entries_->at(from_entry_info_index).addr = to;
+ HashMap::Entry* to_entry = entries_map_.Lookup(to, AddressHash(to),
true);
+ if (to_entry->value != NULL) {
+ int to_entry_info_index =
+ static_cast<int>(reinterpret_cast<intptr_t>(to_entry->value));
+ // 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.
+ entries_->at(to_entry_info_index).addr = NULL;
+ }
+ to_entry->value = reinterpret_cast<void*>(from_entry_info_index);
}
void HeapObjectsMap::AddEntry(Address addr, SnapshotObjectId id) {
HashMap::Entry* entry = entries_map_.Lookup(addr, AddressHash(addr),
true);
ASSERT(entry->value == NULL);
+ ASSERT(entries_->length() > 0 &&
+ entries_->at(0).id == 0 &&
+ entries_->at(0).addr == NULL);
+ ASSERT(entries_->at(entries_->length() - 1).id < id);
entry->value = reinterpret_cast<void*>(entries_->length());
- entries_->Add(EntryInfo(id));
+ entries_->Add(EntryInfo(id, addr));
+ ASSERT(static_cast<uint32_t>(entries_->length()) >
entries_map_.occupancy());
}
@@ -1372,6 +1397,8 @@
static_cast<int>(reinterpret_cast<intptr_t>(entry->value));
EntryInfo& entry_info = entries_->at(entry_index);
entry_info.accessed = true;
+ ASSERT(static_cast<uint32_t>(entries_->length()) >
+ entries_map_.occupancy());
return entry_info.id;
} else {
return 0;
@@ -1380,28 +1407,31 @@
void HeapObjectsMap::RemoveDeadEntries() {
- List<EntryInfo>* new_entries = new List<EntryInfo>();
- List<void*> dead_entries;
- for (HashMap::Entry* entry = entries_map_.Start();
- entry != NULL;
- entry = entries_map_.Next(entry)) {
- int entry_index =
- static_cast<int>(reinterpret_cast<intptr_t>(entry->value));
- EntryInfo& entry_info = entries_->at(entry_index);
+ 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) {
- entry->value = reinterpret_cast<void*>(new_entries->length());
- new_entries->Add(EntryInfo(entry_info.id, false));
+ 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, AddressHash(entry_info.addr), false);
+ ASSERT(entry);
+ entry->value = reinterpret_cast<void*>(first_free_entry);
+ ++first_free_entry;
} else {
- dead_entries.Add(entry->key);
+ if (entry_info.addr) {
+ entries_map_.Remove(entry_info.addr, AddressHash(entry_info.addr));
+ }
}
}
- for (int i = 0; i < dead_entries.length(); ++i) {
- void* raw_entry = dead_entries[i];
- entries_map_.Remove(
- raw_entry, AddressHash(reinterpret_cast<Address>(raw_entry)));
- }
- delete entries_;
- entries_ = new_entries;
+ entries_->Rewind(first_free_entry);
+ ASSERT(static_cast<uint32_t>(entries_->length()) - 1 ==
+ entries_map_.occupancy());
}
=======================================
--- /branches/bleeding_edge/src/profile-generator.h Sun Apr 8 12:18:06 2012
+++ /branches/bleeding_edge/src/profile-generator.h Tue Apr 10 23:58:42 2012
@@ -722,11 +722,12 @@
private:
struct EntryInfo {
- explicit EntryInfo(SnapshotObjectId id) : id(id), accessed(true) { }
- EntryInfo(SnapshotObjectId id, bool accessed)
- : id(id),
- accessed(accessed) { }
+ EntryInfo(SnapshotObjectId id, Address addr)
+ : id(id), addr(addr), accessed(true) { }
+ EntryInfo(SnapshotObjectId id, Address addr, bool accessed)
+ : id(id), addr(addr), accessed(accessed) { }
SnapshotObjectId id;
+ Address addr;
bool accessed;
};
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
