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
diff --git a/runtime/base/hash_map.h b/runtime/base/hash_map.h
new file mode 100644
index 0000000..c0f903f
--- /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 ee2d0b3..5f498d9 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();
}
@@ -45,7 +44,7 @@
for (size_t i = 0; i < len; ++i) {
oss << static_cast<char>('A' + PRand() % 64);
}
- COMPILE_ASSERT(' ' < 'A', must_be_less_than_a);
+ static_assert(' ' < 'A', "space must be less than a");
oss << " " << unique_number_++; // Relies on ' ' < 'A'
return oss.str();
}
@@ -200,4 +199,25 @@
}
}
+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 3704d83..900bc9d 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -128,15 +128,6 @@
}
}
-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;
-}
-
const char* ClassLinker::class_roots_descriptors_[] = {
"Ljava/lang/Class;",
"Ljava/lang/Object;",
@@ -1956,7 +1947,8 @@
}
CHECK(h_class->IsRetired());
// Get the updated class from class table.
- klass = LookupClass(descriptor, h_class.Get()->GetClassLoader());
+ klass = LookupClass(descriptor, ComputeModifiedUtf8Hash(descriptor),
+ h_class.Get()->GetClassLoader());
}
// Wait for the class if it has not already been linked.
@@ -1990,21 +1982,19 @@
// Search a collection of DexFiles for a descriptor
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);
+ 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) ||
@@ -2012,14 +2002,14 @@
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(descriptor, nullptr);
+ mirror::Class* klass = LookupClass(descriptor, hash, nullptr);
if (klass != nullptr) {
return EnsureResolved(self, descriptor, klass);
}
- klass = DefineClass(descriptor, NullHandle<mirror::ClassLoader>(), *pair.first,
+ klass = DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first,
*pair.second);
if (klass != nullptr) {
return klass;
@@ -2067,11 +2057,11 @@
break;
}
for (const DexFile* dex_file : *dex_files) {
- const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor);
+ const DexFile::ClassDef* dex_class_def = dex_file->FindClassDef(descriptor, hash);
if (dex_class_def != nullptr) {
RegisterDexFile(*dex_file);
- mirror::Class* klass =
- DefineClass(descriptor, class_loader, *dex_file, *dex_class_def);
+ mirror::Class* klass = DefineClass(self, descriptor, hash, class_loader, *dex_file,
+ *dex_class_def);
if (klass == nullptr) {
CHECK(self->IsExceptionPending()) << descriptor;
self->ClearException();
@@ -2098,19 +2088,21 @@
// 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(descriptor, class_loader.Get());
+ mirror::Class* klass = LookupClass(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(descriptor, NullHandle<mirror::ClassLoader>(), *pair.first, *pair.second);
+ 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
// expected and will be wrapped in a ClassNotFoundException. Use the pre-allocated error to
@@ -2122,16 +2114,17 @@
} else if (Runtime::Current()->UseCompileTimeClassPath()) {
// First try with the bootstrap class loader.
if (class_loader.Get() != nullptr) {
- klass = LookupClass(descriptor, nullptr);
+ klass = LookupClass(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(descriptor, NullHandle<mirror::ClassLoader>(), *pair.first, *pair.second);
+ return DefineClass(self, descriptor, hash, NullHandle<mirror::ClassLoader>(), *pair.first,
+ *pair.second);
}
// Next try the compile time class path.
const std::vector<const DexFile*>* class_path;
@@ -2141,13 +2134,13 @@
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(descriptor, class_loader, *pair.first, *pair.second);
+ return DefineClass(self, descriptor, hash, class_loader, *pair.first, *pair.second);
}
} else {
ScopedObjectAccessUnchecked soa(self);
- mirror::Class* klass = FindClassInPathClassLoader(soa, self, descriptor, class_loader);
+ mirror::Class* klass = FindClassInPathClassLoader(soa, self, descriptor, hash, class_loader);
if (klass != nullptr) {
return klass;
}
@@ -2186,14 +2179,12 @@
return nullptr;
}
-mirror::Class* ClassLinker::DefineClass(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) {
- Thread* self = Thread::Current();
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_)) {
@@ -2212,14 +2203,10 @@
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
@@ -2244,7 +2231,7 @@
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.
@@ -3039,7 +3026,8 @@
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;
}
@@ -3057,7 +3045,7 @@
// 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]);
@@ -3066,7 +3054,8 @@
if (component_type.Get() == nullptr) {
DCHECK(self->IsExceptionPending());
// We need to accept erroneous classes as component types.
- component_type.Assign(LookupClass(descriptor + 1, class_loader.Get()));
+ const size_t component_hash = ComputeModifiedUtf8Hash(descriptor + 1);
+ component_type.Assign(LookupClass(descriptor + 1, component_hash, class_loader.Get()));
if (component_type.Get() == nullptr) {
DCHECK(self->IsExceptionPending());
return nullptr;
@@ -3096,7 +3085,7 @@
// 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(descriptor, component_type->GetClassLoader());
+ mirror::Class* new_class = LookupClass(descriptor, hash, component_type->GetClassLoader());
if (new_class != nullptr) {
return new_class;
}
@@ -3185,7 +3174,7 @@
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();
}
@@ -3262,21 +3251,18 @@
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_.Find(descriptor);
- CHECK(it != class_table_.end());
-
CHECK(!klass->IsTemp()) << descriptor;
if (kIsDebugBuild && klass->GetClassLoader() == nullptr &&
dex_cache_image_class_lookup_required_) {
@@ -3290,7 +3276,7 @@
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));
}
@@ -3314,8 +3300,8 @@
return false;
}
-mirror::Class* ClassLinker::LookupClass(const char* descriptor, mirror::ClassLoader* class_loader) {
- size_t hash = Hash(descriptor);
+mirror::Class* ClassLinker::LookupClass(const char* descriptor, size_t hash,
+ mirror::ClassLoader* class_loader) {
{
ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
mirror::Class* result = LookupClassFromTableLocked(descriptor, class_loader, hash);
@@ -3383,7 +3369,7 @@
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) << " != "
@@ -3890,7 +3876,8 @@
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();
}
@@ -4450,7 +4437,8 @@
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
@@ -4645,7 +4633,7 @@
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_) {
@@ -4658,7 +4646,7 @@
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];
@@ -5732,7 +5720,7 @@
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,
@@ -5746,7 +5734,7 @@
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()(
@@ -5763,7 +5751,7 @@
}
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 5fdf364..7fc394a 100644
--- a/runtime/class_linker.h
+++ b/runtime/class_linker.h
@@ -76,9 +76,10 @@
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_);
@@ -95,14 +96,15 @@
bool IsInitialized() const;
// Define a new a class based on a ClassDef from a DexFile
- mirror::Class* DefineClass(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(const char* descriptor, mirror::ClassLoader* class_loader)
+ mirror::Class* LookupClass(const char* descriptor, size_t hash,
+ mirror::ClassLoader* class_loader)
LOCKS_EXCLUDED(Locks::classlinker_classes_lock_)
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_);
@@ -444,7 +446,7 @@
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 c783ee4..31d79bf 100644
--- a/runtime/dex_file.cc
+++ b/runtime/dex_file.cc
@@ -413,11 +413,12 @@
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.
@@ -449,11 +450,11 @@
MutexLock mu(Thread::Current(), build_class_def_index_mutex_);
// Are we the first ones building the index?
if (class_def_index_.LoadSequentiallyConsistent() == nullptr) {
- 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* descriptor = GetClassDescriptor(class_def);
- index->insert(std::make_pair(descriptor, &class_def));
+ index->Insert(std::make_pair(descriptor, &class_def));
}
class_def_index_.StoreSequentiallyConsistent(index);
}
diff --git a/runtime/dex_file.h b/runtime/dex_file.h
index 1306f11..54c4b09 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 "globals.h"
@@ -648,8 +649,9 @@
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;
@@ -985,17 +987,30 @@
// 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_;
mutable Mutex build_class_def_index_mutex_ DEFAULT_MUTEX_ACQUIRED_AFTER;
};
diff --git a/runtime/native/dalvik_system_DexFile.cc b/runtime/native/dalvik_system_DexFile.cc
index 2bb59e2..a8b297d 100644
--- a/runtime/native/dalvik_system_DexFile.cc
+++ b/runtime/native/dalvik_system_DexFile.cc
@@ -179,9 +179,9 @@
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();
@@ -189,8 +189,8 @@
StackHandleScope<1> hs(soa.Self());
Handle<mirror::ClassLoader> class_loader(
hs.NewHandle(soa.Decode<mirror::ClassLoader*>(javaLoader)));
- mirror::Class* result = class_linker->DefineClass(descriptor.c_str(), class_loader, *dex_file,
- *dex_class_def);
+ 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;
return soa.AddLocalReference<jclass>(result);
diff --git a/runtime/native/dalvik_system_VMRuntime.cc b/runtime/native/dalvik_system_VMRuntime.cc
index fc1018a..4b1236a 100644
--- a/runtime/native/dalvik_system_VMRuntime.cc
+++ b/runtime/native/dalvik_system_VMRuntime.cc
@@ -254,7 +254,7 @@
if (class_name[1] == '\0') {
klass = linker->FindPrimitiveClass(class_name[0]);
} else {
- klass = linker->LookupClass(class_name, NULL);
+ klass = linker->LookupClass(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 761e800..36b02dc 100644
--- a/runtime/native/java_lang_VMClassLoader.cc
+++ b/runtime/native/java_lang_VMClassLoader.cc
@@ -28,26 +28,28 @@
ScopedFastNativeObjectAccess soa(env);
mirror::ClassLoader* loader = soa.Decode<mirror::ClassLoader*>(javaLoader);
ScopedUtfChars name(env, javaName);
- if (name.c_str() == NULL) {
- return NULL;
+ if (name.c_str() == nullptr) {
+ return nullptr;
}
ClassLinker* cl = Runtime::Current()->GetClassLinker();
std::string descriptor(DotToDescriptor(name.c_str()));
- mirror::Class* c = cl->LookupClass(descriptor.c_str(), loader);
- if (c != NULL && c->IsResolved()) {
+ const size_t descriptor_hash = ComputeModifiedUtf8Hash(descriptor.c_str());
+ mirror::Class* c = cl->LookupClass(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);
}
}
// Class wasn't resolved so it may be erroneous or not yet ready, force the caller to go into
// the regular loadClass code.
- return NULL;
+ return nullptr;
}
static jint VMClassLoader_getBootClassPathSize(JNIEnv*, jclass) {
diff --git a/runtime/utf.cc b/runtime/utf.cc
index 02cbe3b..797c717 100644
--- a/runtime/utf.cc
+++ b/runtime/utf.cc
@@ -85,10 +85,10 @@
return hash;
}
-int32_t ComputeUtf8Hash(const char* chars) {
- int32_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 hash;
}
diff --git a/runtime/utf.h b/runtime/utf.h
index a09db9d..b55227b 100644
--- a/runtime/utf.h
+++ b/runtime/utf.h
@@ -79,8 +79,9 @@
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 63fb2d9..4bb99c1 100644
--- a/runtime/verifier/reg_type_cache.cc
+++ b/runtime/verifier/reg_type_cache.cc
@@ -147,7 +147,7 @@
if (can_load_classes_) {
klass = class_linker->FindClass(self, descriptor, class_loader);
} else {
- klass = class_linker->LookupClass(descriptor, loader);
+ klass = class_linker->LookupClass(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;