diff options
author | Mathieu Chartier <mathieuc@google.com> | 2014-11-06 16:35:45 -0800 |
---|---|---|
committer | Mathieu Chartier <mathieuc@google.com> | 2014-11-07 11:45:06 -0800 |
commit | e7c9a8c2b8481aafbc6af4ce6229bd361ba24742 (patch) | |
tree | f6d8fe8fd7aeae117a6547dc4f012cd4085cb4e8 | |
parent | 00b2da5c02339c36ffa4006f731f55203b09265d (diff) | |
download | android_art-e7c9a8c2b8481aafbc6af4ce6229bd361ba24742.tar.gz android_art-e7c9a8c2b8481aafbc6af4ce6229bd361ba24742.tar.bz2 android_art-e7c9a8c2b8481aafbc6af4ce6229bd361ba24742.zip |
Add hash map, reduce excessive hashing
Changed the class def index to use a HashMap instead of unordered_map
so that we can use FindWithHash to reduce how often we need to compute
hashes.
Fixed a bug in ClassLinker::UpdateClass where we didn't properly
handle classes with the same descriptor but different class loaders.
Introduced by previous CL.
Before (fb launch):
1.74% art::ComputeModifiedUtf8Hash(char const*)
After:
0.95% art::ComputeModifiedUtf8Hash(char const*)
Bug: 18054905
Bug: 16828525
Change-Id: Iba2ee37c9837289e0ea187800ba4af322225a994
(cherry picked from commit 564ff985184737977aa26c485d0c1a413e530705)
-rw-r--r-- | oatdump/oatdump.cc | 3 | ||||
-rw-r--r-- | runtime/base/hash_map.h | 60 | ||||
-rw-r--r-- | runtime/base/hash_set_test.cc | 26 | ||||
-rw-r--r-- | runtime/class_linker.cc | 117 | ||||
-rw-r--r-- | runtime/class_linker.h | 11 | ||||
-rw-r--r-- | runtime/dex_file.cc | 9 | ||||
-rw-r--r-- | runtime/dex_file.h | 23 | ||||
-rw-r--r-- | runtime/native/dalvik_system_DexFile.cc | 6 | ||||
-rw-r--r-- | runtime/native/dalvik_system_VMRuntime.cc | 2 | ||||
-rw-r--r-- | runtime/native/java_lang_VMClassLoader.cc | 6 | ||||
-rw-r--r-- | runtime/utf.cc | 6 | ||||
-rw-r--r-- | runtime/utf.h | 5 | ||||
-rw-r--r-- | runtime/verifier/reg_type_cache.cc | 3 |
13 files changed, 183 insertions, 94 deletions
diff --git a/oatdump/oatdump.cc b/oatdump/oatdump.cc index dca048fb85..cdf48c360c 100644 --- a/oatdump/oatdump.cc +++ b/oatdump/oatdump.cc @@ -520,8 +520,9 @@ class OatDumper { LOG(WARNING) << "Failed to open dex file '" << oat_dex_file->GetDexFileLocation() << "': " << error_msg; } else { + const char* descriptor = m->GetDeclaringClassDescriptor(); const DexFile::ClassDef* class_def = - dex_file->FindClassDef(m->GetDeclaringClassDescriptor()); + dex_file->FindClassDef(descriptor, ComputeModifiedUtf8Hash(descriptor)); if (class_def != nullptr) { uint16_t class_def_index = dex_file->GetIndexForClassDef(*class_def); const OatFile::OatClass oat_class = oat_dex_file->GetOatClass(class_def_index); diff --git a/runtime/base/hash_map.h b/runtime/base/hash_map.h new file mode 100644 index 0000000000..c0f903f51f --- /dev/null +++ b/runtime/base/hash_map.h @@ -0,0 +1,60 @@ +/* + * Copyright (C) 2014 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. + */ + +#ifndef ART_RUNTIME_BASE_HASH_MAP_H_ +#define ART_RUNTIME_BASE_HASH_MAP_H_ + +#include <utility> + +#include "hash_set.h" + +namespace art { + +template <typename Fn> +class HashMapWrapper { + public: + // Hash function. + template <class Key, class Value> + size_t operator()(const std::pair<Key, Value>& pair) const { + return fn_(pair.first); + } + template <class Key> + size_t operator()(const Key& key) const { + return fn_(key); + } + template <class Key, class Value> + bool operator()(const std::pair<Key, Value>& a, const std::pair<Key, Value>& b) const { + return fn_(a.first, b.first); + } + template <class Key, class Value, class Element> + bool operator()(const std::pair<Key, Value>& a, const Element& element) const { + return fn_(a.first, element); + } + + private: + Fn fn_; +}; + +template <class Key, class Value, class EmptyFn = DefaultEmptyFn<Key>, + class HashFn = std::hash<Key>, class Pred = std::equal_to<Key>, + class Alloc = std::allocator<std::pair<Key, Value>>> +class HashMap : public HashSet<std::pair<Key, Value>, EmptyFn, HashMapWrapper<HashFn>, + HashMapWrapper<Pred>, Alloc> { +}; + +} // namespace art + +#endif // ART_RUNTIME_BASE_HASH_MAP_H_ diff --git a/runtime/base/hash_set_test.cc b/runtime/base/hash_set_test.cc index 885fc06b79..5f498d9c78 100644 --- a/runtime/base/hash_set_test.cc +++ b/runtime/base/hash_set_test.cc @@ -22,12 +22,11 @@ #include <unordered_set> #include "common_runtime_test.h" -#include "utils.h" +#include "hash_map.h" namespace art { -class IsEmptyFnString { - public: +struct IsEmptyFnString { void MakeEmpty(std::string& item) const { item.clear(); } @@ -200,4 +199,25 @@ TEST_F(HashSetTest, TestStress) { } } +struct IsEmptyStringPair { + void MakeEmpty(std::pair<std::string, int>& pair) const { + pair.first.clear(); + } + bool IsEmpty(const std::pair<std::string, int>& pair) const { + return pair.first.empty(); + } +}; + +TEST_F(HashSetTest, TestHashMap) { + HashMap<std::string, int, IsEmptyStringPair> hash_map; + hash_map.Insert(std::make_pair(std::string("abcd"), 123)); + hash_map.Insert(std::make_pair(std::string("abcd"), 124)); + hash_map.Insert(std::make_pair(std::string("bags"), 444)); + auto it = hash_map.Find(std::string("abcd")); + ASSERT_EQ(it->second, 123); + hash_map.Erase(it); + it = hash_map.Find(std::string("abcd")); + ASSERT_EQ(it->second, 124); +} + } // namespace art diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc index fecea89933..fb90b911bd 100644 --- a/runtime/class_linker.cc +++ b/runtime/class_linker.cc @@ -147,15 +147,6 @@ static void WrapExceptionInInitializer(Handle<mirror::Class> klass) VlogClassInitializationFailure(klass); } -static size_t Hash(const char* s) { - // This is the java.lang.String hashcode for convenience, not interoperability. - size_t hash = 0; - for (; *s != '\0'; ++s) { - hash = hash * 31 + *s; - } - return hash; -} - // Gap between two fields in object layout. struct FieldGap { uint32_t start_offset; // The offset from the start of the object. @@ -2010,7 +2001,8 @@ mirror::Class* ClassLinker::EnsureResolved(Thread* self, const char* descriptor, } CHECK(h_class->IsRetired()); // Get the updated class from class table. - klass = LookupClass(self, descriptor, h_class.Get()->GetClassLoader()); + klass = LookupClass(self, descriptor, ComputeModifiedUtf8Hash(descriptor), + h_class.Get()->GetClassLoader()); } // Wait for the class if it has not already been linked. @@ -2043,22 +2035,20 @@ mirror::Class* ClassLinker::EnsureResolved(Thread* self, const char* descriptor, typedef std::pair<const DexFile*, const DexFile::ClassDef*> ClassPathEntry; // Search a collection of DexFiles for a descriptor -static ClassPathEntry FindInClassPath(const char* descriptor, - const std::vector<const DexFile*>& class_path) { - for (size_t i = 0; i != class_path.size(); ++i) { - const DexFile* dex_file = class_path[i]; - const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor); +ClassPathEntry FindInClassPath(const char* descriptor, + size_t hash, const std::vector<const DexFile*>& class_path) { + for (const DexFile* dex_file : class_path) { + const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor, hash); if (dex_class_def != nullptr) { return ClassPathEntry(dex_file, dex_class_def); } } - // TODO: remove reinterpret_cast when issue with -std=gnu++0x host issue resolved - return ClassPathEntry(static_cast<const DexFile*>(nullptr), - static_cast<const DexFile::ClassDef*>(nullptr)); + return ClassPathEntry(nullptr, nullptr); } mirror::Class* ClassLinker::FindClassInPathClassLoader(ScopedObjectAccessAlreadyRunnable& soa, Thread* self, const char* descriptor, + size_t hash, Handle<mirror::ClassLoader> class_loader) { if (class_loader->GetClass() != soa.Decode<mirror::Class*>(WellKnownClasses::dalvik_system_PathClassLoader) || @@ -2066,14 +2056,14 @@ mirror::Class* ClassLinker::FindClassInPathClassLoader(ScopedObjectAccessAlready soa.Decode<mirror::Class*>(WellKnownClasses::java_lang_BootClassLoader)) { return nullptr; } - ClassPathEntry pair = FindInClassPath(descriptor, boot_class_path_); + ClassPathEntry pair = FindInClassPath(descriptor, hash, boot_class_path_); // Check if this would be found in the parent boot class loader. if (pair.second != nullptr) { - mirror::Class* klass = LookupClass(self, descriptor, nullptr); + mirror::Class* klass = LookupClass(self, descriptor, hash, nullptr); if (klass != nullptr) { return EnsureResolved(self, descriptor, klass); } - klass = DefineClass(self, descriptor, NullHandle<mirror::ClassLoader>(), *pair.first, + klass = DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first, *pair.second); if (klass != nullptr) { return klass; @@ -2121,11 +2111,11 @@ mirror::Class* ClassLinker::FindClassInPathClassLoader(ScopedObjectAccessAlready break; } for (const DexFile* cp_dex_file : *dex_files) { - const DexFile::ClassDef* dex_class_def = cp_dex_file->FindClassDef(descriptor); + const DexFile::ClassDef* dex_class_def = cp_dex_file->FindClassDef(descriptor, hash); if (dex_class_def != nullptr) { RegisterDexFile(*cp_dex_file); - mirror::Class* klass = - DefineClass(self, descriptor, class_loader, *cp_dex_file, *dex_class_def); + mirror::Class* klass = DefineClass(self, descriptor, hash, class_loader, + *cp_dex_file, *dex_class_def); if (klass == nullptr) { CHECK(self->IsExceptionPending()) << descriptor; self->ClearException(); @@ -2152,19 +2142,20 @@ mirror::Class* ClassLinker::FindClass(Thread* self, const char* descriptor, // for primitive classes that aren't backed by dex files. return FindPrimitiveClass(descriptor[0]); } + const size_t hash = ComputeModifiedUtf8Hash(descriptor); // Find the class in the loaded classes table. - mirror::Class* klass = LookupClass(self, descriptor, class_loader.Get()); + mirror::Class* klass = LookupClass(self, descriptor, hash, class_loader.Get()); if (klass != nullptr) { return EnsureResolved(self, descriptor, klass); } // Class is not yet loaded. if (descriptor[0] == '[') { - return CreateArrayClass(self, descriptor, class_loader); + return CreateArrayClass(self, descriptor, hash, class_loader); } else if (class_loader.Get() == nullptr) { // The boot class loader, search the boot class path. - ClassPathEntry pair = FindInClassPath(descriptor, boot_class_path_); + ClassPathEntry pair = FindInClassPath(descriptor, hash, boot_class_path_); if (pair.second != nullptr) { - return DefineClass(self, descriptor, NullHandle<mirror::ClassLoader>(), *pair.first, + return DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first, *pair.second); } else { // The boot class loader is searched ahead of the application class loader, failures are @@ -2177,16 +2168,16 @@ mirror::Class* ClassLinker::FindClass(Thread* self, const char* descriptor, } else if (Runtime::Current()->UseCompileTimeClassPath()) { // First try with the bootstrap class loader. if (class_loader.Get() != nullptr) { - klass = LookupClass(self, descriptor, nullptr); + klass = LookupClass(self, descriptor, hash, nullptr); if (klass != nullptr) { return EnsureResolved(self, descriptor, klass); } } // If the lookup failed search the boot class path. We don't perform a recursive call to avoid // a NoClassDefFoundError being allocated. - ClassPathEntry pair = FindInClassPath(descriptor, boot_class_path_); + ClassPathEntry pair = FindInClassPath(descriptor, hash, boot_class_path_); if (pair.second != nullptr) { - return DefineClass(self, descriptor, NullHandle<mirror::ClassLoader>(), *pair.first, + return DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first, *pair.second); } // Next try the compile time class path. @@ -2197,9 +2188,9 @@ mirror::Class* ClassLinker::FindClass(Thread* self, const char* descriptor, soa.AddLocalReference<jobject>(class_loader.Get())); class_path = &Runtime::Current()->GetCompileTimeClassPath(jclass_loader.get()); } - pair = FindInClassPath(descriptor, *class_path); + pair = FindInClassPath(descriptor, hash, *class_path); if (pair.second != nullptr) { - return DefineClass(self, descriptor, class_loader, *pair.first, *pair.second); + return DefineClass(self, descriptor, hash, class_loader, *pair.first, *pair.second); } else { // Use the pre-allocated NCDFE at compile time to avoid wasting time constructing exceptions. mirror::Throwable* pre_allocated = Runtime::Current()->GetPreAllocatedNoClassDefFoundError(); @@ -2208,7 +2199,8 @@ mirror::Class* ClassLinker::FindClass(Thread* self, const char* descriptor, } } else { ScopedObjectAccessUnchecked soa(self); - mirror::Class* cp_klass = FindClassInPathClassLoader(soa, self, descriptor, class_loader); + mirror::Class* cp_klass = FindClassInPathClassLoader(soa, self, descriptor, hash, + class_loader); if (cp_klass != nullptr) { return cp_klass; } @@ -2245,13 +2237,12 @@ mirror::Class* ClassLinker::FindClass(Thread* self, const char* descriptor, UNREACHABLE(); } -mirror::Class* ClassLinker::DefineClass(Thread* self, const char* descriptor, +mirror::Class* ClassLinker::DefineClass(Thread* self, const char* descriptor, size_t hash, Handle<mirror::ClassLoader> class_loader, const DexFile& dex_file, const DexFile::ClassDef& dex_class_def) { StackHandleScope<3> hs(self); auto klass = hs.NewHandle<mirror::Class>(nullptr); - bool should_allocate = false; // Load the class from the dex file. if (UNLIKELY(!init_done_)) { @@ -2270,14 +2261,10 @@ mirror::Class* ClassLinker::DefineClass(Thread* self, const char* descriptor, klass.Assign(GetClassRoot(kJavaLangReflectArtField)); } else if (strcmp(descriptor, "Ljava/lang/reflect/ArtMethod;") == 0) { klass.Assign(GetClassRoot(kJavaLangReflectArtMethod)); - } else { - should_allocate = true; } - } else { - should_allocate = true; } - if (should_allocate) { + if (klass.Get() == nullptr) { // Allocate a class with the status of not ready. // Interface object should get the right size here. Regular class will // figure out the right size later and be replaced with one of the right @@ -2302,7 +2289,7 @@ mirror::Class* ClassLinker::DefineClass(Thread* self, const char* descriptor, klass->SetClinitThreadId(self->GetTid()); // Add the newly loaded class to the loaded classes table. - mirror::Class* existing = InsertClass(descriptor, klass.Get(), Hash(descriptor)); + mirror::Class* existing = InsertClass(descriptor, klass.Get(), hash); if (existing != nullptr) { // We failed to insert because we raced with another thread. Calling EnsureResolved may cause // this thread to block. @@ -3106,7 +3093,8 @@ mirror::Class* ClassLinker::InitializePrimitiveClass(mirror::Class* primitive_cl primitive_class->SetPrimitiveType(type); primitive_class->SetStatus(mirror::Class::kStatusInitialized, self); const char* descriptor = Primitive::Descriptor(type); - mirror::Class* existing = InsertClass(descriptor, primitive_class, Hash(descriptor)); + mirror::Class* existing = InsertClass(descriptor, primitive_class, + ComputeModifiedUtf8Hash(descriptor)); CHECK(existing == nullptr) << "InitPrimitiveClass(" << type << ") failed"; return primitive_class; } @@ -3124,7 +3112,7 @@ mirror::Class* ClassLinker::InitializePrimitiveClass(mirror::Class* primitive_cl // array class; that always comes from the base element class. // // Returns nullptr with an exception raised on failure. -mirror::Class* ClassLinker::CreateArrayClass(Thread* self, const char* descriptor, +mirror::Class* ClassLinker::CreateArrayClass(Thread* self, const char* descriptor, size_t hash, Handle<mirror::ClassLoader> class_loader) { // Identify the underlying component type CHECK_EQ('[', descriptor[0]); @@ -3134,7 +3122,8 @@ mirror::Class* ClassLinker::CreateArrayClass(Thread* self, const char* descripto if (component_type.Get() == nullptr) { DCHECK(self->IsExceptionPending()); // We need to accept erroneous classes as component types. - component_type.Assign(LookupClass(self, descriptor + 1, class_loader.Get())); + const size_t component_hash = ComputeModifiedUtf8Hash(descriptor + 1); + component_type.Assign(LookupClass(self, descriptor + 1, component_hash, class_loader.Get())); if (component_type.Get() == nullptr) { DCHECK(self->IsExceptionPending()); return nullptr; @@ -3164,7 +3153,7 @@ mirror::Class* ClassLinker::CreateArrayClass(Thread* self, const char* descripto // class to the hash table --- necessary because of possible races with // other threads.) if (class_loader.Get() != component_type->GetClassLoader()) { - mirror::Class* new_class = LookupClass(self, descriptor, component_type->GetClassLoader()); + mirror::Class* new_class = LookupClass(self, descriptor, hash, component_type->GetClassLoader()); if (new_class != nullptr) { return new_class; } @@ -3253,7 +3242,7 @@ mirror::Class* ClassLinker::CreateArrayClass(Thread* self, const char* descripto new_class->SetAccessFlags(access_flags); - mirror::Class* existing = InsertClass(descriptor, new_class.Get(), Hash(descriptor)); + mirror::Class* existing = InsertClass(descriptor, new_class.Get(), hash); if (existing == nullptr) { return new_class.Get(); } @@ -3330,21 +3319,18 @@ mirror::Class* ClassLinker::InsertClass(const char* descriptor, mirror::Class* k mirror::Class* ClassLinker::UpdateClass(const char* descriptor, mirror::Class* klass, size_t hash) { WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_); - mirror::Class* existing = - LookupClassFromTableLocked(descriptor, klass->GetClassLoader(), hash); - - if (existing == nullptr) { + auto existing_it = class_table_.FindWithHash(std::make_pair(descriptor, klass->GetClassLoader()), + hash); + if (existing_it == class_table_.end()) { CHECK(klass->IsProxyClass()); return nullptr; } + mirror::Class* existing = existing_it->Read(); CHECK_NE(existing, klass) << descriptor; CHECK(!existing->IsResolved()) << descriptor; CHECK_EQ(klass->GetStatus(), mirror::Class::kStatusResolving) << descriptor; - auto it = class_table_.FindWithHash(GcRoot<mirror::Class>(klass), hash); - CHECK(it != class_table_.end()); - CHECK(!klass->IsTemp()) << descriptor; if (kIsDebugBuild && klass->GetClassLoader() == nullptr && dex_cache_image_class_lookup_required_) { @@ -3358,7 +3344,7 @@ mirror::Class* ClassLinker::UpdateClass(const char* descriptor, mirror::Class* k VerifyObject(klass); // Update the element in the hash set. - *it = GcRoot<mirror::Class>(klass); + *existing_it = GcRoot<mirror::Class>(klass); if (log_new_class_table_roots_) { new_class_roots_.push_back(GcRoot<mirror::Class>(klass)); } @@ -3382,9 +3368,8 @@ bool ClassLinker::RemoveClass(const char* descriptor, mirror::ClassLoader* class return false; } -mirror::Class* ClassLinker::LookupClass(Thread* self, const char* descriptor, +mirror::Class* ClassLinker::LookupClass(Thread* self, const char* descriptor, size_t hash, mirror::ClassLoader* class_loader) { - size_t hash = Hash(descriptor); { ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_); mirror::Class* result = LookupClassFromTableLocked(descriptor, class_loader, hash); @@ -3451,7 +3436,7 @@ void ClassLinker::MoveImageClassesToClassTable() { if (klass != nullptr) { DCHECK(klass->GetClassLoader() == nullptr); const char* descriptor = klass->GetDescriptor(&temp); - size_t hash = Hash(descriptor); + size_t hash = ComputeModifiedUtf8Hash(descriptor); mirror::Class* existing = LookupClassFromTableLocked(descriptor, nullptr, hash); if (existing != nullptr) { CHECK_EQ(existing, klass) << PrettyClassAndClassLoader(existing) << " != " @@ -3952,7 +3937,8 @@ mirror::Class* ClassLinker::CreateProxyClass(ScopedObjectAccessAlreadyRunnable& CHECK_EQ(klass.Get()->GetThrows(), soa.Decode<mirror::ObjectArray<mirror::ObjectArray<mirror::Class>>*>(throws)); } - mirror::Class* existing = InsertClass(descriptor.c_str(), klass.Get(), Hash(descriptor.c_str())); + mirror::Class* existing = InsertClass(descriptor.c_str(), klass.Get(), + ComputeModifiedUtf8Hash(descriptor.c_str())); CHECK(existing == nullptr); return klass.Get(); } @@ -4499,7 +4485,8 @@ bool ClassLinker::LinkClass(Thread* self, const char* descriptor, Handle<mirror: FixupTemporaryDeclaringClass(klass.Get(), new_class_h.Get()); - mirror::Class* existing = UpdateClass(descriptor, new_class_h.Get(), Hash(descriptor)); + mirror::Class* existing = UpdateClass(descriptor, new_class_h.Get(), + ComputeModifiedUtf8Hash(descriptor)); CHECK(existing == nullptr || existing == klass.Get()); // This will notify waiters on temp class that saw the not yet resolved class in the @@ -4695,7 +4682,7 @@ class LinkVirtualHashTable { void Add(uint32_t virtual_method_index) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { mirror::ArtMethod* local_method = klass_->GetVirtualMethodDuringLinking(virtual_method_index); const char* name = local_method->GetName(); - uint32_t hash = Hash(name); + uint32_t hash = ComputeModifiedUtf8Hash(name); uint32_t index = hash % hash_size_; // Linear probe until we have an empty slot. while (hash_table_[index] != invalid_index_) { @@ -4708,7 +4695,7 @@ class LinkVirtualHashTable { uint32_t FindAndRemove(MethodNameAndSignatureComparator* comparator) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) { const char* name = comparator->GetName(); - uint32_t hash = Hash(name); + uint32_t hash = ComputeModifiedUtf8Hash(name); size_t index = hash % hash_size_; while (true) { const uint32_t value = hash_table_[index]; @@ -5888,7 +5875,7 @@ const char* ClassLinker::GetClassRootDescriptor(ClassRoot class_root) { std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& root) const { std::string temp; - return Hash(root.Read()->GetDescriptor(&temp)); + return ComputeModifiedUtf8Hash(root.Read()->GetDescriptor(&temp)); } bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& a, @@ -5902,7 +5889,7 @@ bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Cla std::size_t ClassLinker::ClassDescriptorHashEquals::operator()( const std::pair<const char*, mirror::ClassLoader*>& element) const { - return Hash(element.first); + return ComputeModifiedUtf8Hash(element.first); } bool ClassLinker::ClassDescriptorHashEquals::operator()( @@ -5919,7 +5906,7 @@ bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Cla } std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const char* descriptor) const { - return Hash(descriptor); + return ComputeModifiedUtf8Hash(descriptor); } } // namespace art diff --git a/runtime/class_linker.h b/runtime/class_linker.h index 7b2ba43b67..385f135192 100644 --- a/runtime/class_linker.h +++ b/runtime/class_linker.h @@ -117,9 +117,10 @@ class ClassLinker { Handle<mirror::ClassLoader> class_loader) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); - // Find a class in the path class loader, loading it if necessary. + // Find a class in the path class loader, loading it if necessary. Hash function is supposed to + // be ComputeModifiedUtf8Hash(descriptor). mirror::Class* FindClassInPathClassLoader(ScopedObjectAccessAlreadyRunnable& soa, - Thread* self, const char* descriptor, + Thread* self, const char* descriptor, size_t hash, Handle<mirror::ClassLoader> class_loader) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); @@ -138,14 +139,14 @@ class ClassLinker { } // Define a new a class based on a ClassDef from a DexFile - mirror::Class* DefineClass(Thread* self, const char* descriptor, + mirror::Class* DefineClass(Thread* self, const char* descriptor, size_t hash, Handle<mirror::ClassLoader> class_loader, const DexFile& dex_file, const DexFile::ClassDef& dex_class_def) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); // Finds a class by its descriptor, returning NULL if it isn't wasn't loaded // by the given 'class_loader'. - mirror::Class* LookupClass(Thread* self, const char* descriptor, + mirror::Class* LookupClass(Thread* self, const char* descriptor, size_t hash, mirror::ClassLoader* class_loader) LOCKS_EXCLUDED(Locks::classlinker_classes_lock_) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); @@ -499,7 +500,7 @@ class ClassLinker { SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); - mirror::Class* CreateArrayClass(Thread* self, const char* descriptor, + mirror::Class* CreateArrayClass(Thread* self, const char* descriptor, size_t hash, Handle<mirror::ClassLoader> class_loader) SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); diff --git a/runtime/dex_file.cc b/runtime/dex_file.cc index 16bc33f76a..3d4184bd5f 100644 --- a/runtime/dex_file.cc +++ b/runtime/dex_file.cc @@ -419,11 +419,12 @@ uint32_t DexFile::GetVersion() const { return atoi(version); } -const DexFile::ClassDef* DexFile::FindClassDef(const char* descriptor) const { +const DexFile::ClassDef* DexFile::FindClassDef(const char* descriptor, size_t hash) const { + DCHECK_EQ(ComputeModifiedUtf8Hash(descriptor), hash); // If we have an index lookup the descriptor via that as its constant time to search. Index* index = class_def_index_.LoadSequentiallyConsistent(); if (index != nullptr) { - auto it = index->find(descriptor); + auto it = index->FindWithHash(descriptor, hash); return (it == index->end()) ? nullptr : it->second; } // Fast path for rate no class defs case. @@ -455,11 +456,11 @@ const DexFile::ClassDef* DexFile::FindClassDef(const char* descriptor) const { // Are we the ones moving the miss count past the max? Sanity check the index doesn't exist. CHECK(class_def_index_.LoadSequentiallyConsistent() == nullptr); // Build the index. - index = new Index(num_class_defs); + index = new Index(); for (uint32_t i = 0; i < num_class_defs; ++i) { const ClassDef& class_def = GetClassDef(i); const char* class_descriptor = GetClassDescriptor(class_def); - index->insert(std::make_pair(class_descriptor, &class_def)); + index->Insert(std::make_pair(class_descriptor, &class_def)); } // Sanity check the index still doesn't exist, only 1 thread should build it. CHECK(class_def_index_.LoadSequentiallyConsistent() == nullptr); diff --git a/runtime/dex_file.h b/runtime/dex_file.h index 8ced664633..a71ca429cb 100644 --- a/runtime/dex_file.h +++ b/runtime/dex_file.h @@ -22,6 +22,7 @@ #include <unordered_map> #include <vector> +#include "base/hash_map.h" #include "base/logging.h" #include "base/mutex.h" // For Locks::mutator_lock_. #include "base/value_object.h" @@ -649,8 +650,9 @@ class DexFile { return StringByTypeIdx(class_def.class_idx_); } - // Looks up a class definition by its class descriptor. - const ClassDef* FindClassDef(const char* descriptor) const; + // Looks up a class definition by its class descriptor. Hash must be + // ComputeModifiedUtf8Hash(descriptor). + const ClassDef* FindClassDef(const char* descriptor, size_t hash) const; // Looks up a class definition by its type index. const ClassDef* FindClassDef(uint16_t type_idx) const; @@ -986,17 +988,30 @@ class DexFile { // Number of misses finding a class def from a descriptor. mutable Atomic<uint32_t> find_class_def_misses_; + struct UTF16EmptyFn { + void MakeEmpty(std::pair<const char*, const ClassDef*>& pair) const { + pair.first = nullptr; + pair.second = nullptr; + } + bool IsEmpty(const std::pair<const char*, const ClassDef*>& pair) const { + if (pair.first == nullptr) { + DCHECK(pair.second == nullptr); + return true; + } + return false; + } + }; struct UTF16HashCmp { // Hash function. size_t operator()(const char* key) const { - return ComputeUtf8Hash(key); + return ComputeModifiedUtf8Hash(key); } // std::equal function. bool operator()(const char* a, const char* b) const { return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(a, b) == 0; } }; - typedef std::unordered_map<const char*, const ClassDef*, UTF16HashCmp, UTF16HashCmp> Index; + typedef HashMap<const char*, const ClassDef*, UTF16EmptyFn, UTF16HashCmp, UTF16HashCmp> Index; mutable Atomic<Index*> class_def_index_; }; std::ostream& operator<<(std::ostream& os, const DexFile& dex_file); diff --git a/runtime/native/dalvik_system_DexFile.cc b/runtime/native/dalvik_system_DexFile.cc index 012e03e051..f37312efa7 100644 --- a/runtime/native/dalvik_system_DexFile.cc +++ b/runtime/native/dalvik_system_DexFile.cc @@ -185,9 +185,9 @@ static jclass DexFile_defineClassNative(JNIEnv* env, jclass, jstring javaName, j return NULL; } const std::string descriptor(DotToDescriptor(class_name.c_str())); - + const size_t hash(ComputeModifiedUtf8Hash(descriptor.c_str())); for (const DexFile* dex_file : *dex_files) { - const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor.c_str()); + const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor.c_str(), hash); if (dex_class_def != nullptr) { ScopedObjectAccess soa(env); ClassLinker* class_linker = Runtime::Current()->GetClassLinker(); @@ -195,7 +195,7 @@ static jclass DexFile_defineClassNative(JNIEnv* env, jclass, jstring javaName, j StackHandleScope<1> hs(soa.Self()); Handle<mirror::ClassLoader> class_loader( hs.NewHandle(soa.Decode<mirror::ClassLoader*>(javaLoader))); - mirror::Class* result = class_linker->DefineClass(soa.Self(), descriptor.c_str(), + mirror::Class* result = class_linker->DefineClass(soa.Self(), descriptor.c_str(), hash, class_loader, *dex_file, *dex_class_def); if (result != nullptr) { VLOG(class_linker) << "DexFile_defineClassNative returning " << result diff --git a/runtime/native/dalvik_system_VMRuntime.cc b/runtime/native/dalvik_system_VMRuntime.cc index fdba43ed8b..f6e2b218fc 100644 --- a/runtime/native/dalvik_system_VMRuntime.cc +++ b/runtime/native/dalvik_system_VMRuntime.cc @@ -262,7 +262,7 @@ static void PreloadDexCachesResolveType(Thread* self, mirror::DexCache* dex_cach if (class_name[1] == '\0') { klass = linker->FindPrimitiveClass(class_name[0]); } else { - klass = linker->LookupClass(self, class_name, NULL); + klass = linker->LookupClass(self, class_name, ComputeModifiedUtf8Hash(class_name), NULL); } if (klass == NULL) { return; diff --git a/runtime/native/java_lang_VMClassLoader.cc b/runtime/native/java_lang_VMClassLoader.cc index 45563d299c..35932e0b89 100644 --- a/runtime/native/java_lang_VMClassLoader.cc +++ b/runtime/native/java_lang_VMClassLoader.cc @@ -36,14 +36,16 @@ static jclass VMClassLoader_findLoadedClass(JNIEnv* env, jclass, jobject javaLoa } ClassLinker* cl = Runtime::Current()->GetClassLinker(); std::string descriptor(DotToDescriptor(name.c_str())); - mirror::Class* c = cl->LookupClass(soa.Self(), descriptor.c_str(), loader); + const size_t descriptor_hash = ComputeModifiedUtf8Hash(descriptor.c_str()); + mirror::Class* c = cl->LookupClass(soa.Self(), descriptor.c_str(), descriptor_hash, loader); if (c != nullptr && c->IsResolved()) { return soa.AddLocalReference<jclass>(c); } if (loader != nullptr) { // Try the common case. StackHandleScope<1> hs(soa.Self()); - c = cl->FindClassInPathClassLoader(soa, soa.Self(), descriptor.c_str(), hs.NewHandle(loader)); + c = cl->FindClassInPathClassLoader(soa, soa.Self(), descriptor.c_str(), descriptor_hash, + hs.NewHandle(loader)); if (c != nullptr) { return soa.AddLocalReference<jclass>(c); } diff --git a/runtime/utf.cc b/runtime/utf.cc index 735815d76d..05b847b806 100644 --- a/runtime/utf.cc +++ b/runtime/utf.cc @@ -85,10 +85,10 @@ int32_t ComputeUtf16Hash(const uint16_t* chars, size_t char_count) { return static_cast<int32_t>(hash); } -int32_t ComputeUtf8Hash(const char* chars) { - uint32_t hash = 0; +size_t ComputeModifiedUtf8Hash(const char* chars) { + size_t hash = 0; while (*chars != '\0') { - hash = hash * 31 + GetUtf16FromUtf8(&chars); + hash = hash * 31 + *chars++; } return static_cast<int32_t>(hash); } diff --git a/runtime/utf.h b/runtime/utf.h index a09db9d54b..b55227bc4a 100644 --- a/runtime/utf.h +++ b/runtime/utf.h @@ -79,8 +79,9 @@ int32_t ComputeUtf16Hash(mirror::CharArray* chars, int32_t offset, size_t char_c SHARED_LOCKS_REQUIRED(Locks::mutator_lock_); int32_t ComputeUtf16Hash(const uint16_t* chars, size_t char_count); -// Compute a hash code of a UTF-8 string. -int32_t ComputeUtf8Hash(const char* chars); +// Compute a hash code of a modified UTF-8 string. Not the standard java hash since it returns a +// size_t and hashes individual chars instead of codepoint words. +size_t ComputeModifiedUtf8Hash(const char* chars); /* * Retrieve the next UTF-16 character from a UTF-8 string. diff --git a/runtime/verifier/reg_type_cache.cc b/runtime/verifier/reg_type_cache.cc index 7c4094574f..1dfbe510bc 100644 --- a/runtime/verifier/reg_type_cache.cc +++ b/runtime/verifier/reg_type_cache.cc @@ -148,7 +148,8 @@ mirror::Class* RegTypeCache::ResolveClass(const char* descriptor, mirror::ClassL if (can_load_classes_) { klass = class_linker->FindClass(self, descriptor, class_loader); } else { - klass = class_linker->LookupClass(self, descriptor, loader); + klass = class_linker->LookupClass(self, descriptor, ComputeModifiedUtf8Hash(descriptor), + loader); if (klass != nullptr && !klass->IsLoaded()) { // We found the class but without it being loaded its not safe for use. klass = nullptr; |