ART: Switch to name-based IMT hashing

Use a hash scheme based on the name. This keeps IMT slots stable
when dex tables change.

This incurs a severe performance penalty for computing the slot.
Measurements on host degraded from 30ns to an average of 85mus.
However, calls in compiled code will not incur this overhead.

Added a test comparing similar interfaces in similar dex files.

Bug: 31594153
Test: test-art-host
Change-Id: Ibb86679ee94bec561984ea25826e56b1a7964cd0

8 files changed, 247 insertions, 12 deletions

diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 850702ad23..4f273e5979 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -29,6 +29,8 @@ GTEST_DEX_DIRECTORIES := \
   GetMethodSignature \
   ImageLayoutA \
   ImageLayoutB \
+  IMTA \
+  IMTB \
   Instrumentation \
   Interfaces \
   Lookup \
@@ -88,6 +90,7 @@ ART_GTEST_dex_file_test_DEX_DEPS := GetMethodSignature Main Nested
 ART_GTEST_dex2oat_test_DEX_DEPS := $(ART_GTEST_dex2oat_environment_tests_DEX_DEPS) Statics
 ART_GTEST_exception_test_DEX_DEPS := ExceptionHandle
 ART_GTEST_image_test_DEX_DEPS := ImageLayoutA ImageLayoutB
+ART_GTEST_imtable_test_DEX_DEPS := IMTA IMTB
 ART_GTEST_instrumentation_test_DEX_DEPS := Instrumentation
 ART_GTEST_jni_compiler_test_DEX_DEPS := MyClassNatives
 ART_GTEST_jni_internal_test_DEX_DEPS := AllFields StaticLeafMethods
@@ -593,6 +596,7 @@ ART_GTEST_dex_file_test_DEX_DEPS :=
 ART_GTEST_exception_test_DEX_DEPS :=
 ART_GTEST_elf_writer_test_HOST_DEPS :=
 ART_GTEST_elf_writer_test_TARGET_DEPS :=
+ART_GTEST_imtable_test_DEX_DEPS :=
 ART_GTEST_jni_compiler_test_DEX_DEPS :=
 ART_GTEST_jni_internal_test_DEX_DEPS :=
 ART_GTEST_oat_file_assistant_test_DEX_DEPS :=
diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc
index f75841415e..2fcc0cfc89 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -2864,10 +2864,17 @@ class IMTDumper {
         std::cerr << "  " << iface->GetDescriptor(&iface_name) << std::endl;
 
         for (ArtMethod& iface_method : iface->GetVirtualMethods(pointer_size)) {
-          uint32_t base_hash = ImTable::GetBaseImtHash(&iface_method);
+          uint32_t class_hash, name_hash, signature_hash;
+          ImTable::GetImtHashComponents(&iface_method, &class_hash, &name_hash, &signature_hash);
           uint32_t imt_slot = ImTable::GetImtIndex(&iface_method);
-          std::cerr << "    " << PrettyMethod(&iface_method, true) << " slot=" << std::dec
-              << imt_slot << " base_hash=0x" << std::hex << base_hash << std::endl;
+          std::cerr << "    " << PrettyMethod(&iface_method, true)
+              << " slot=" << imt_slot
+              << std::hex
+              << " class_hash=0x" << class_hash
+              << " name_hash=0x" << name_hash
+              << " signature_hash=0x" << signature_hash
+              << std::dec
+              << std::endl;
         }
       }
     }
diff --git a/runtime/Android.bp b/runtime/Android.bp
index 31f2490c21..6945eb0802 100644
--- a/runtime/Android.bp
+++ b/runtime/Android.bp
@@ -536,6 +536,7 @@ art_cc_test {
         "gc/task_processor_test.cc",
         "gtest_test.cc",
         "handle_scope_test.cc",
+        "imtable_test.cc",
         "indenter_test.cc",
         "indirect_reference_table_test.cc",
         "instrumentation_test.cc",
diff --git a/runtime/imtable-inl.h b/runtime/imtable-inl.h
index 0cb9b5e4dc..cb85fa6e56 100644
--- a/runtime/imtable-inl.h
+++ b/runtime/imtable-inl.h
@@ -20,15 +20,82 @@
 #include "imtable.h"
 
 #include "art_method-inl.h"
+#include "dex_file.h"
+#include "utf.h"
 
 namespace art {
 
-inline uint32_t ImTable::GetBaseImtHash(ArtMethod* method) REQUIRES_SHARED(Locks::mutator_lock_) {
-  return method->GetDexMethodIndex();
+static constexpr bool kImTableHashUseName = true;
+static constexpr bool kImTableHashUseCoefficients = true;
+
+// Magic configuration that minimizes some common runtime calls.
+static constexpr uint32_t kImTableHashCoefficientClass = 427;
+static constexpr uint32_t kImTableHashCoefficientName = 16;
+static constexpr uint32_t kImTableHashCoefficientSignature = 14;
+
+inline void ImTable::GetImtHashComponents(ArtMethod* method,
+                                          uint32_t* class_hash,
+                                          uint32_t* name_hash,
+                                          uint32_t* signature_hash) {
+  if (kImTableHashUseName) {
+    if (method->IsProxyMethod()) {
+      *class_hash = 0;
+      *name_hash = 0;
+      *signature_hash = 0;
+      return;
+    }
+
+    const DexFile* dex_file = method->GetDexFile();
+    const DexFile::MethodId& method_id = dex_file->GetMethodId(method->GetDexMethodIndex());
+
+    // Class descriptor for the class component.
+    *class_hash = ComputeModifiedUtf8Hash(dex_file->GetMethodDeclaringClassDescriptor(method_id));
+
+    // Method name for the method component.
+    *name_hash = ComputeModifiedUtf8Hash(dex_file->GetMethodName(method_id));
+
+    const DexFile::ProtoId& proto_id = dex_file->GetMethodPrototype(method_id);
+
+    // Read the proto for the signature component.
+    uint32_t tmp = ComputeModifiedUtf8Hash(
+        dex_file->GetTypeDescriptor(dex_file->GetTypeId(proto_id.return_type_idx_)));
+
+    // Mix in the argument types.
+    // Note: we could consider just using the shorty. This would be faster, at the price of
+    //       potential collisions.
+    const DexFile::TypeList* param_types = dex_file->GetProtoParameters(proto_id);
+    if (param_types != nullptr) {
+      for (size_t i = 0; i != param_types->Size(); ++i) {
+        const DexFile::TypeItem& type = param_types->GetTypeItem(i);
+        tmp = 31 * tmp + ComputeModifiedUtf8Hash(
+            dex_file->GetTypeDescriptor(dex_file->GetTypeId(type.type_idx_)));
+      }
+    }
+
+    *signature_hash = tmp;
+    return;
+  } else {
+    *class_hash = method->GetDexMethodIndex();
+    *name_hash = 0;
+    *signature_hash = 0;
+    return;
+  }
 }
 
 inline uint32_t ImTable::GetImtIndex(ArtMethod* method) {
-  return GetBaseImtHash(method) % ImTable::kSize;
+  uint32_t class_hash, name_hash, signature_hash;
+  GetImtHashComponents(method, &class_hash, &name_hash, &signature_hash);
+
+  uint32_t mixed_hash;
+  if (!kImTableHashUseCoefficients) {
+    mixed_hash = class_hash + name_hash + signature_hash;
+  } else {
+    mixed_hash = kImTableHashCoefficientClass * class_hash +
+                 kImTableHashCoefficientName * name_hash +
+                 kImTableHashCoefficientSignature * signature_hash;
+  }
+
+  return mixed_hash % ImTable::kSize;
 }
 
 }  // namespace art
diff --git a/runtime/imtable.h b/runtime/imtable.h
index 6df890d14b..b7066bd521 100644
--- a/runtime/imtable.h
+++ b/runtime/imtable.h
@@ -23,6 +23,7 @@
 
 #include "base/enums.h"
 #include "base/macros.h"
+#include "base/mutex.h"
 
 namespace art {
 
@@ -74,18 +75,17 @@ class ImTable {
     return kSize * static_cast<size_t>(pointer_size);
   }
 
-  // Converts a method to the base hash used in GetImtIndex.
-  ALWAYS_INLINE static inline uint32_t GetBaseImtHash(ArtMethod* method)
-      REQUIRES_SHARED(Locks::mutator_lock_);
-  ALWAYS_INLINE static inline uint32_t GetBaseImtHash(const DexFile* dex_file, uint32_t method_idx)
+  // Converts a method to the base hash components used in GetImtIndex.
+  ALWAYS_INLINE static inline void GetImtHashComponents(ArtMethod* method,
+                                                        uint32_t* class_hash,
+                                                        uint32_t* name_hash,
+                                                        uint32_t* signature_hash)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   // The (complete) hashing scheme to map an ArtMethod to a slot in the Interface Method Table
   // (IMT).
   ALWAYS_INLINE static inline uint32_t GetImtIndex(ArtMethod* method)
       REQUIRES_SHARED(Locks::mutator_lock_);
-  ALWAYS_INLINE static inline uint32_t GetImtIndex(const DexFile* dex_file, uint32_t method_idx)
-      REQUIRES_SHARED(Locks::mutator_lock_);
 };
 
 }  // namespace art
diff --git a/runtime/imtable_test.cc b/runtime/imtable_test.cc
new file mode 100644
index 0000000000..8cbe2916ec
--- /dev/null
+++ b/runtime/imtable_test.cc
@@ -0,0 +1,104 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "imtable-inl.h"
+
+#include <memory>
+#include <string>
+
+#include "jni.h"
+
+#include "base/mutex.h"
+#include "class_linker.h"
+#include "common_runtime_test.h"
+#include "mirror/accessible_object.h"
+#include "mirror/class.h"
+#include "mirror/class_loader.h"
+#include "handle_scope-inl.h"
+#include "scoped_thread_state_change-inl.h"
+#include "thread-inl.h"
+
+namespace art {
+
+class ImTableTest : public CommonRuntimeTest {
+ public:
+  std::pair<mirror::Class*, mirror::Class*> LoadClasses(const std::string& class_name)
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    jobject jclass_loader_a = LoadDex("IMTA");
+    CHECK(jclass_loader_a != nullptr);
+    jobject jclass_loader_b = LoadDex("IMTB");
+    CHECK(jclass_loader_b != nullptr);
+
+    ClassLinker* class_linker = Runtime::Current()->GetClassLinker();
+    Thread* self = Thread::Current();
+
+    StackHandleScope<3> hs(self);
+    MutableHandle<mirror::ClassLoader> h_class_loader = hs.NewHandle<mirror::ClassLoader>(nullptr);
+
+    // A.
+    h_class_loader.Assign(
+        ObjPtr<mirror::ClassLoader>::DownCast(self->DecodeJObject(jclass_loader_a)));
+    Handle<mirror::Class> h_class_a(
+          hs.NewHandle(class_linker->FindClass(self, class_name.c_str(), h_class_loader)));
+    if (h_class_a.Get() == nullptr) {
+      LOG(ERROR) << self->GetException()->Dump();
+      CHECK(false) << "h_class_a == nullptr";
+    }
+
+    // B.
+    h_class_loader.Assign(
+        ObjPtr<mirror::ClassLoader>::DownCast(self->DecodeJObject(jclass_loader_b)));
+    Handle<mirror::Class> h_class_b(
+          hs.NewHandle(class_linker->FindClass(self, class_name.c_str(), h_class_loader)));
+    if (h_class_b.Get() == nullptr) {
+      LOG(ERROR) << self->GetException()->Dump();
+      CHECK(false) << "h_class_b == nullptr";
+    }
+
+    return std::make_pair(h_class_a.Get(), h_class_b.Get());
+  }
+
+  std::pair<ArtMethod*, ArtMethod*> LoadMethods(const std::string& class_name,
+                                                const std::string& method_name)
+      REQUIRES_SHARED(Locks::mutator_lock_) {
+    std::pair<mirror::Class*, mirror::Class*> classes = LoadClasses(class_name);
+
+    const PointerSize pointer_size = Runtime::Current()->GetClassLinker()->GetImagePointerSize();
+
+    ArtMethod* method_a =
+        classes.first->FindDeclaredVirtualMethodByName(method_name, pointer_size);
+    ArtMethod* method_b =
+        classes.second->FindDeclaredVirtualMethodByName(method_name, pointer_size);
+
+    return std::make_pair(method_a, method_b);
+  }
+};
+
+TEST_F(ImTableTest, NewMethodBefore) {
+  ScopedObjectAccess soa(Thread::Current());
+
+  std::pair<ArtMethod*, ArtMethod*> methods = LoadMethods("LInterfaces$A;", "foo");
+  CHECK_EQ(ImTable::GetImtIndex(methods.first), ImTable::GetImtIndex(methods.second));
+}
+
+TEST_F(ImTableTest, NewClassBefore) {
+  ScopedObjectAccess soa(Thread::Current());
+
+  std::pair<ArtMethod*, ArtMethod*> methods = LoadMethods("LInterfaces$Z;", "foo");
+  CHECK_EQ(ImTable::GetImtIndex(methods.first), ImTable::GetImtIndex(methods.second));
+}
+
+}  // namespace art
diff --git a/test/IMTA/Interfaces.java b/test/IMTA/Interfaces.java
new file mode 100644
index 0000000000..4322f157e5
--- /dev/null
+++ b/test/IMTA/Interfaces.java
@@ -0,0 +1,24 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+class Interfaces {
+    interface A {
+        public void foo();
+    }
+    interface Z {
+        public void foo();
+    }
+}
diff --git a/test/IMTB/Interfaces.java b/test/IMTB/Interfaces.java
new file mode 100644
index 0000000000..f252624d9c
--- /dev/null
+++ b/test/IMTB/Interfaces.java
@@ -0,0 +1,28 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+class Interfaces {
+    interface A {
+        public void bar();
+        public void foo();
+    }
+    interface L {
+        public void foo();
+    }
+    interface Z {
+        public void foo();
+    }
+}