Implement a hash based look-up to speed up containing address check in large

src/spaces.cc

Index: src/spaces.cc
===================================================================
--- src/spaces.cc	(revision 10961)
+++ src/spaces.cc	(working copy)
@@ -2520,7 +2520,11 @@
 
 // -----------------------------------------------------------------------------
 // LargeObjectSpace
+static bool ComparePointers(void* key1, void* key2) {
+    return key1 == key2;
+}
 
+
 LargeObjectSpace::LargeObjectSpace(Heap* heap,
                                    intptr_t max_capacity,
                                    AllocationSpace id)
@@ -2529,7 +2533,8 @@
       first_page_(NULL),
       size_(0),
       page_count_(0),
-      objects_size_(0) {}
+      objects_size_(0),
+      chunk_map_(ComparePointers, 1024) {}
 
 
 bool LargeObjectSpace::SetUp() {
@@ -2537,6 +2542,7 @@
   size_ = 0;
   page_count_ = 0;
   objects_size_ = 0;
+  chunk_map_.Clear();
   return true;
 }
 
@@ -2580,6 +2586,17 @@
   page->set_next_page(first_page_);
   first_page_ = page;
 
+  // Register all MemoryChunk::kAlignment-aligned chunks covered by
+  // this large page in the chunk map.
+  uint32_t base = reinterpret_cast<uint32_t>(page)/MemoryChunk::kAlignment;

[Vyacheslav Egorov (Chromium), 2012/03/09 12:15:37]

casting page to uint32_t is not suitable for 64-bit arch.

consider using uintptr_t instead.

[kewpie.w.zp, 2012/03/12 02:00:40]

Done.

+  uint32_t limit = base + (page->size()-1)/MemoryChunk::kAlignment;
+  for (uint32_t key = base; key <= limit; key++) {
+    HashMap::Entry* entry = chunk_map_.Lookup(reinterpret_cast<void*>(key),
+                                              key, true);
+    ASSERT(entry != NULL);
+    entry->value = page;
+  }
+
   HeapObject* object = page->GetObject();
 
 #ifdef DEBUG
@@ -2596,27 +2613,25 @@
 
 // GC support
 MaybeObject* LargeObjectSpace::FindObject(Address a) {
-  for (LargePage* page = first_page_;
-       page != NULL;
-       page = page->next_page()) {
-    Address page_address = page->address();
-    if (page_address <= a && a < page_address + page->size()) {
-      return page->GetObject();
-    }
+  LargePage* page = FindPageContainingPc(a);

[Vyacheslav Egorov (Chromium), 2012/03/09 12:15:37]

I would suggest retaining FindPageContainingPc because you are calling it from
the function that is used for arbitrary addresses.

[kewpie.w.zp, 2012/03/12 02:00:40]

Not very sure if I catch your point. Please allow me to confirm. Do you suggest
retaining the linear search of FindPageContainingPc() and just change
FindObject() to hash lookup, or reversed, or something else ? Thanks a lot for
your answering

[Vyacheslav Egorov (Chromium), 2012/03/12 12:04:12]

My original comment should read: "I would suggest _renaming_...". Sorry for the
confusion, there was a typo.

My point was that there is nothing PC or code object specific in the code.

[kewpie.w.zp, 2012/03/13 01:44:35]

I see. Maybe it's named so because called by
InnerPointerToCodeCache::GcSafeFindCodeForInnerPointer(). How about change to
"FindPage(Address a)", or something else you'd like to recommend ? 

[Vyacheslav Egorov (Chromium), 2012/03/13 11:39:11]

FindPage sounds good to me

+  if (page != NULL) {
+    return page->GetObject();
   }
   return Failure::Exception();
 }
 
 
 LargePage* LargeObjectSpace::FindPageContainingPc(Address pc) {
-  // TODO(853): Change this implementation to only find executable
-  // chunks and use some kind of hash-based approach to speed it up.
-  for (LargePage* chunk = first_page_;
-       chunk != NULL;
-       chunk = chunk->next_page()) {
-    Address chunk_address = chunk->address();
-    if (chunk_address <= pc && pc < chunk_address + chunk->size()) {
-      return chunk;
+  uint32_t key = reinterpret_cast<uint32_t>(pc) / MemoryChunk::kAlignment;
+  HashMap::Entry* e = chunk_map_.Lookup(reinterpret_cast<void*>(key),
+                                        key, false);
+  if (e != NULL) {
+    ASSERT(e->value != NULL);
+    LargePage* page = reinterpret_cast<LargePage*>(e->value);
+    ASSERT(page->is_valid());
+    Address page_address = page->address();
+    if (page_address <= pc && pc < page_address + page->size()) {

[Vyacheslav Egorov (Chromium), 2012/03/09 12:15:37]

Consider using page->Contains(pc) here.

[kewpie.w.zp, 2012/03/12 02:00:40]

The check range of page->Contains(pc) falls into (base+Page::kObjectStartOffset,
base+chunk_size), so if pc falls into page's header range (base,
base+Page::kObjectStartOffset) will be failed, which would succeed otherwise.
Should we allow this difference and replace it with Contains() anyway ? 

[Vyacheslav Egorov (Chromium), 2012/03/12 12:04:12]

I don't think anybody should pass addresses that fall outside of inner object
area to this function. If anybody does --- that is clearly a bug.

[kewpie.w.zp, 2012/03/13 01:44:35]

Done.

+      return page;
     }
   }
   return NULL;
@@ -2654,6 +2669,13 @@
       objects_size_ -= object->Size();
       page_count_--;
 
+      // Remove entries belonging to this page.
+      uint32_t base = reinterpret_cast<uint32_t>(page)/MemoryChunk::kAlignment;

[Vyacheslav Egorov (Chromium), 2012/03/09 12:15:37]

casting page to uint32_t is not suitable for 64-bit arch.

consider using uintptr_t instead.

[kewpie.w.zp, 2012/03/12 02:00:40]

Done.

+      uint32_t limit = base + (page->size()-1)/MemoryChunk::kAlignment;
+      for (uint32_t key = base; key <= limit; key++) {
+        chunk_map_.Remove(reinterpret_cast<void*>(key), key);
+      }
+
       if (is_pointer_object) {
         heap()->QueueMemoryChunkForFree(page);
       } else {