ART: Change vtable check implementation
Trade space for performance and use a (pseudo-)linear implementation
for CheckVTableHasNoDuplicates.
The new algorithm has a first pass that attempts to check under the
assumption that all entries are from the same dex file, and a second
pass dedicated for the cross-dex-file case.
Both passes use maps to store discovered information and detect
duplicates via existing entries. The code is complicated by an effort
to reduce repeated hashing overhead.
Decreases dex2oatd preopting of a big app from 150s to 35s.
Bug: 123888325
Test: m test-art-host
Change-Id: I3e5e3c8ccfeaf94b89b045eb691ec88556399ae6
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index ef0d72f..46ae545 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -25,6 +25,7 @@
#include <memory>
#include <queue>
#include <string>
+#include <string_view>
#include <tuple>
#include <unordered_map>
#include <utility>
@@ -7040,11 +7041,13 @@
return FindSameNameAndSignature(cmp, rest...);
}
+namespace {
+
// Check that all vtable entries are present in this class's virtuals or are the same as a
// superclasses vtable entry.
-static void CheckClassOwnsVTableEntries(Thread* self,
- Handle<mirror::Class> klass,
- PointerSize pointer_size)
+void CheckClassOwnsVTableEntries(Thread* self,
+ Handle<mirror::Class> klass,
+ PointerSize pointer_size)
REQUIRES_SHARED(Locks::mutator_lock_) {
StackHandleScope<2> hs(self);
Handle<mirror::PointerArray> check_vtable(hs.NewHandle(klass->GetVTableDuringLinking()));
@@ -7075,43 +7078,165 @@
// Check to make sure the vtable does not have duplicates. Duplicates could cause problems when a
// method is overridden in a subclass.
template <PointerSize kPointerSize>
-static void CheckVTableHasNoDuplicates(Thread* self, Handle<mirror::Class> klass)
+void CheckVTableHasNoDuplicates(Thread* self, Handle<mirror::Class> klass)
REQUIRES_SHARED(Locks::mutator_lock_) {
StackHandleScope<1> hs(self);
Handle<mirror::PointerArray> vtable(hs.NewHandle(klass->GetVTableDuringLinking()));
int32_t num_entries = vtable->GetLength();
- for (int32_t i = 0; i < num_entries; i++) {
- ArtMethod* vtable_entry = vtable->GetElementPtrSize<ArtMethod*, kPointerSize>(i);
- // Don't bother if we cannot 'see' the vtable entry (i.e. it is a package-private member maybe).
+
+ // Observations:
+ // * The older implementation was O(n^2) and got too expensive for apps with larger classes.
+ // * Many classes do not override Object functions (e.g., equals/hashCode/toString). Thus,
+ // for many classes outside of libcore a cross-dexfile check has to be run anyways.
+ // * In the cross-dexfile case, with the O(n^2), in the best case O(n) cross checks would have
+ // to be done. It is thus OK in a single-pass algorithm to read all data, anyways.
+ // * The single-pass algorithm will trade memory for speed, but that is OK.
+
+ CHECK_GT(num_entries, 0);
+
+ auto log_fn = [&vtable, &klass](int32_t i, int32_t j) REQUIRES_SHARED(Locks::mutator_lock_) {
+ ArtMethod* m1 = vtable->GetElementPtrSize<ArtMethod*, kPointerSize>(i);
+ ArtMethod* m2 = vtable->GetElementPtrSize<ArtMethod*, kPointerSize>(j);
+ LOG(WARNING) << "vtable entries " << i << " and " << j << " are identical for "
+ << klass->PrettyClass() << " in method " << m1->PrettyMethod()
+ << " (0x" << std::hex << reinterpret_cast<uintptr_t>(m2) << ") and "
+ << m2->PrettyMethod() << " (0x" << std::hex
+ << reinterpret_cast<uintptr_t>(m2) << ")";
+ };
+ struct BaseHashType {
+ static size_t HashCombine(size_t seed, size_t val) {
+ return seed ^ (val + 0x9e3779b9 + (seed << 6) + (seed >> 2));
+ }
+ };
+
+ // Check assuming all entries come from the same dex file.
+ {
+ // Find the first interesting method and its dex file.
+ int32_t start = 0;
+ for (; start < num_entries; ++start) {
+ ArtMethod* vtable_entry = vtable->GetElementPtrSize<ArtMethod*, kPointerSize>(start);
+ // Don't bother if we cannot 'see' the vtable entry (i.e. it is a package-private member
+ // maybe).
+ if (!klass->CanAccessMember(vtable_entry->GetDeclaringClass(),
+ vtable_entry->GetAccessFlags())) {
+ continue;
+ }
+ break;
+ }
+ if (start == num_entries) {
+ return;
+ }
+ const DexFile* dex_file =
+ vtable->GetElementPtrSize<ArtMethod*, kPointerSize>(start)->
+ GetInterfaceMethodIfProxy(kPointerSize)->GetDexFile();
+
+ // Helper function to avoid logging if we have to run the cross-file checks.
+ auto check_fn = [&](bool log_warn) REQUIRES_SHARED(Locks::mutator_lock_) {
+ // Use a map to store seen entries, as the storage space is too large for a bitvector.
+ using PairType = std::pair<uint32_t, uint16_t>;
+ struct PairHash : BaseHashType {
+ size_t operator()(const PairType& key) const {
+ return BaseHashType::HashCombine(BaseHashType::HashCombine(0, key.first), key.second);
+ }
+ };
+ std::unordered_map<PairType, int32_t, PairHash> seen;
+ seen.reserve(2 * num_entries);
+ bool need_slow_path = false;
+ bool found_dup = false;
+ for (int i = start; i < num_entries; ++i) {
+ // Can use Unchecked here as the start loop already ensured that the arrays are correct
+ // wrt/ kPointerSize.
+ ArtMethod* vtable_entry = vtable->GetElementPtrSizeUnchecked<ArtMethod*, kPointerSize>(i);
+ if (!klass->CanAccessMember(vtable_entry->GetDeclaringClass(),
+ vtable_entry->GetAccessFlags())) {
+ continue;
+ }
+ ArtMethod* m = vtable_entry->GetInterfaceMethodIfProxy(kPointerSize);
+ if (dex_file != m->GetDexFile()) {
+ need_slow_path = true;
+ break;
+ }
+ const dex::MethodId* m_mid = &dex_file->GetMethodId(m->GetDexMethodIndex());
+ PairType pair = std::make_pair(m_mid->name_idx_.index_, m_mid->proto_idx_.index_);
+ auto it = seen.find(pair);
+ if (it != seen.end()) {
+ found_dup = true;
+ if (log_warn) {
+ log_fn(it->second, i);
+ }
+ } else {
+ seen.emplace(pair, i);
+ }
+ }
+ return std::make_pair(need_slow_path, found_dup);
+ };
+ std::pair<bool, bool> result = check_fn(/* log_warn= */ false);
+ if (!result.first) {
+ if (result.second) {
+ check_fn(/* log_warn= */ true);
+ }
+ return;
+ }
+ }
+
+ // Need to check across dex files.
+ struct Entry {
+ size_t cached_hash = 0;
+ const char* name = nullptr;
+ Signature signature = Signature::NoSignature();
+ uint32_t name_len = 0;
+
+ Entry(const DexFile* dex_file, const dex::MethodId& mid)
+ : name(dex_file->StringDataAndUtf16LengthByIdx(mid.name_idx_, &name_len)),
+ signature(dex_file->GetMethodSignature(mid)) {
+ }
+
+ bool operator==(const Entry& other) const {
+ if (name_len != other.name_len || strcmp(name, other.name) != 0) {
+ return false;
+ }
+ return signature == other.signature;
+ }
+ };
+ struct EntryHash {
+ size_t operator()(const Entry& key) const {
+ return key.cached_hash;
+ }
+ };
+ std::unordered_map<Entry, int32_t, EntryHash> map;
+ for (int32_t i = 0; i < num_entries; ++i) {
+ // Can use Unchecked here as the first loop already ensured that the arrays are correct
+ // wrt/ kPointerSize.
+ ArtMethod* vtable_entry = vtable->GetElementPtrSizeUnchecked<ArtMethod*, kPointerSize>(i);
+ // Don't bother if we cannot 'see' the vtable entry (i.e. it is a package-private member
+ // maybe).
if (!klass->CanAccessMember(vtable_entry->GetDeclaringClass(),
vtable_entry->GetAccessFlags())) {
continue;
}
- MethodNameAndSignatureComparator name_comparator(
- vtable_entry->GetInterfaceMethodIfProxy(kPointerSize));
- for (int32_t j = i + 1; j < num_entries; j++) {
- // Can use Unchecked here as the outer loop already ensured that the arrays are correct
- // wrt/ kPointerSize.
- ArtMethod* other_entry = vtable->GetElementPtrSizeUnchecked<ArtMethod*, kPointerSize>(j);
- if (!klass->CanAccessMember(other_entry->GetDeclaringClass(),
- other_entry->GetAccessFlags())) {
- continue;
- }
- if (vtable_entry == other_entry ||
- name_comparator.HasSameNameAndSignature(
- other_entry->GetInterfaceMethodIfProxy(kPointerSize))) {
- LOG(WARNING) << "vtable entries " << i << " and " << j << " are identical for "
- << klass->PrettyClass() << " in method " << vtable_entry->PrettyMethod()
- << " (0x" << std::hex << reinterpret_cast<uintptr_t>(vtable_entry) << ") and "
- << other_entry->PrettyMethod() << " (0x" << std::hex
- << reinterpret_cast<uintptr_t>(other_entry) << ")";
- }
+ ArtMethod* m = vtable_entry->GetInterfaceMethodIfProxy(kPointerSize);
+ const DexFile* dex_file = m->GetDexFile();
+ const dex::MethodId& mid = dex_file->GetMethodId(m->GetDexMethodIndex());
+
+ Entry e(dex_file, mid);
+
+ size_t string_hash = std::hash<std::string_view>()(std::string_view(e.name, e.name_len));
+ size_t sig_hash = std::hash<std::string>()(e.signature.ToString());
+ e.cached_hash = BaseHashType::HashCombine(BaseHashType::HashCombine(0u, string_hash),
+ sig_hash);
+
+ auto it = map.find(e);
+ if (it != map.end()) {
+ log_fn(it->second, i);
+ } else {
+ map.emplace(e, i);
}
}
}
-static void CheckVTableHasNoDuplicates(Thread* self,
- Handle<mirror::Class> klass,
- PointerSize pointer_size)
+
+void CheckVTableHasNoDuplicates(Thread* self,
+ Handle<mirror::Class> klass,
+ PointerSize pointer_size)
REQUIRES_SHARED(Locks::mutator_lock_) {
switch (pointer_size) {
case PointerSize::k64:
@@ -7129,6 +7254,8 @@
CheckVTableHasNoDuplicates(self, klass, pointer_size);
}
+} // namespace
+
void ClassLinker::FillImtFromSuperClass(Handle<mirror::Class> klass,
ArtMethod* unimplemented_method,
ArtMethod* imt_conflict_method,
