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
(cherry picked from commit 49d0a7d4009b77e19f3b2129fe01631c4764ae5c)
diff --git a/build/Android.gtest.mk b/build/Android.gtest.mk
index 4f63099..c9448ab 100644
--- a/build/Android.gtest.mk
+++ b/build/Android.gtest.mk
@@ -29,6 +29,8 @@
GetMethodSignature \
ImageLayoutA \
ImageLayoutB \
+ IMTA \
+ IMTB \
Instrumentation \
Interfaces \
Lookup \
@@ -87,6 +89,7 @@
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
@@ -592,6 +595,7 @@
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 be5224b..fefaa9e 100644
--- a/oatdump/oatdump.cc
+++ b/oatdump/oatdump.cc
@@ -2858,10 +2858,17 @@
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 31f2490..6945eb0 100644
--- a/runtime/Android.bp
+++ b/runtime/Android.bp
@@ -536,6 +536,7 @@
"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 0cb9b5e..cb85fa6 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 6df890d..b7066bd 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 @@
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 0000000..ff45114
--- /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(
+ reinterpret_cast<mirror::ClassLoader*>(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(
+ reinterpret_cast<mirror::ClassLoader*>(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 0000000..4322f15
--- /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 0000000..f252624
--- /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();
+ }
+}
