Add hash set
More memory efficient than libcxx since we do not box the values.
Change intern table to use new hash set. Clean up intern table by
removing const casts and deleting unnecessary code.
Changed the class linker to use a hash set, also added a pre-zygote
class table.
5 samples of:
adb shell stop && adb shell start && sleep 60 && adb shell dumpsys meminfo
Before:
165929 kB: Native
175859 kB: Native
168434 kB: Native
166559 kB: Native
169958 kB: Native
After:
160972 kB: Native
159439 kB: Native
157204 kB: Native
165093 kB: Native
163039 kB: Native
TODO: Add HashTable which is implemented by using a HashSet.
TODO: Use for DexFile::find_class_def_misses_.
TODO: Investigate using mem maps instead of native heap.
Bug: 17808975
Change-Id: I93e376cf6eb9628cf52f4aefdadb6157acfb799a
(cherry picked from commit e05d1d5fd86867afc7513b1c546375dba11eee50)
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index eeb65f9..fecea89 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -1730,25 +1730,24 @@
void ClassLinker::VisitClassRoots(RootCallback* callback, void* arg, VisitRootFlags flags) {
WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
if ((flags & kVisitRootFlagAllRoots) != 0) {
- for (std::pair<const size_t, GcRoot<mirror::Class> >& it : class_table_) {
- it.second.VisitRoot(callback, arg, 0, kRootStickyClass);
+ for (GcRoot<mirror::Class>& root : class_table_) {
+ root.VisitRoot(callback, arg, 0, kRootStickyClass);
+ }
+ for (GcRoot<mirror::Class>& root : pre_zygote_class_table_) {
+ root.VisitRoot(callback, arg, 0, kRootStickyClass);
}
} else if ((flags & kVisitRootFlagNewRoots) != 0) {
- for (auto& pair : new_class_roots_) {
- mirror::Class* old_ref = pair.second.Read<kWithoutReadBarrier>();
- pair.second.VisitRoot(callback, arg, 0, kRootStickyClass);
- mirror::Class* new_ref = pair.second.Read<kWithoutReadBarrier>();
+ for (auto& root : new_class_roots_) {
+ mirror::Class* old_ref = root.Read<kWithoutReadBarrier>();
+ root.VisitRoot(callback, arg, 0, kRootStickyClass);
+ mirror::Class* new_ref = root.Read<kWithoutReadBarrier>();
if (UNLIKELY(new_ref != old_ref)) {
// Uh ohes, GC moved a root in the log. Need to search the class_table and update the
// corresponding object. This is slow, but luckily for us, this may only happen with a
// concurrent moving GC.
- for (auto it = class_table_.lower_bound(pair.first), end = class_table_.end();
- it != end && it->first == pair.first; ++it) {
- // If the class stored matches the old class, update it to the new value.
- if (old_ref == it->second.Read<kWithoutReadBarrier>()) {
- it->second = GcRoot<mirror::Class>(new_ref);
- }
- }
+ auto it = class_table_.Find(GcRoot<mirror::Class>(old_ref));
+ class_table_.Erase(it);
+ class_table_.Insert(GcRoot<mirror::Class>(new_ref));
}
}
}
@@ -1806,9 +1805,13 @@
}
// TODO: why isn't this a ReaderMutexLock?
WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
- for (std::pair<const size_t, GcRoot<mirror::Class> >& it : class_table_) {
- mirror::Class* c = it.second.Read();
- if (!visitor(c, arg)) {
+ for (GcRoot<mirror::Class>& root : class_table_) {
+ if (!visitor(root.Read(), arg)) {
+ return;
+ }
+ }
+ for (GcRoot<mirror::Class>& root : pre_zygote_class_table_) {
+ if (!visitor(root.Read(), arg)) {
return;
}
}
@@ -1864,7 +1867,7 @@
size_t class_table_size;
{
ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
- class_table_size = class_table_.size();
+ class_table_size = class_table_.Size() + pre_zygote_class_table_.Size();
}
mirror::Class* class_type = mirror::Class::GetJavaLangClass();
mirror::Class* array_of_class = FindArrayClass(self, &class_type);
@@ -3303,8 +3306,7 @@
LOG(INFO) << "Loaded class " << descriptor << source;
}
WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
- mirror::Class* existing =
- LookupClassFromTableLocked(descriptor, klass->GetClassLoader(), hash);
+ mirror::Class* existing = LookupClassFromTableLocked(descriptor, klass->GetClassLoader(), hash);
if (existing != nullptr) {
return existing;
}
@@ -3314,13 +3316,13 @@
// is in the image.
existing = LookupClassFromImage(descriptor);
if (existing != nullptr) {
- CHECK(klass == existing);
+ CHECK_EQ(klass, existing);
}
}
VerifyObject(klass);
- class_table_.insert(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+ class_table_.InsertWithHash(GcRoot<mirror::Class>(klass), hash);
if (log_new_class_table_roots_) {
- new_class_roots_.push_back(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+ new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
}
return nullptr;
}
@@ -3340,14 +3342,8 @@
CHECK(!existing->IsResolved()) << descriptor;
CHECK_EQ(klass->GetStatus(), mirror::Class::kStatusResolving) << descriptor;
- for (auto it = class_table_.lower_bound(hash), end = class_table_.end();
- it != end && it->first == hash; ++it) {
- mirror::Class* klass_from_table = it->second.Read();
- if (klass_from_table == existing) {
- class_table_.erase(it);
- break;
- }
- }
+ auto it = class_table_.FindWithHash(GcRoot<mirror::Class>(klass), hash);
+ CHECK(it != class_table_.end());
CHECK(!klass->IsTemp()) << descriptor;
if (kIsDebugBuild && klass->GetClassLoader() == nullptr &&
@@ -3356,36 +3352,38 @@
// is in the image.
existing = LookupClassFromImage(descriptor);
if (existing != nullptr) {
- CHECK(klass == existing) << descriptor;
+ CHECK_EQ(klass, existing) << descriptor;
}
}
VerifyObject(klass);
- class_table_.insert(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+ // Update the element in the hash set.
+ *it = GcRoot<mirror::Class>(klass);
if (log_new_class_table_roots_) {
- new_class_roots_.push_back(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+ new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
}
return existing;
}
-bool ClassLinker::RemoveClass(const char* descriptor, const mirror::ClassLoader* class_loader) {
- size_t hash = Hash(descriptor);
+bool ClassLinker::RemoveClass(const char* descriptor, mirror::ClassLoader* class_loader) {
WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
- for (auto it = class_table_.lower_bound(hash), end = class_table_.end();
- it != end && it->first == hash;
- ++it) {
- mirror::Class* klass = it->second.Read();
- if (klass->GetClassLoader() == class_loader && klass->DescriptorEquals(descriptor)) {
- class_table_.erase(it);
- return true;
- }
+ auto pair = std::make_pair(descriptor, class_loader);
+ auto it = class_table_.Find(pair);
+ if (it != class_table_.end()) {
+ class_table_.Erase(it);
+ return true;
+ }
+ it = pre_zygote_class_table_.Find(pair);
+ if (it != pre_zygote_class_table_.end()) {
+ pre_zygote_class_table_.Erase(it);
+ return true;
}
return false;
}
mirror::Class* ClassLinker::LookupClass(Thread* self, const char* descriptor,
- const mirror::ClassLoader* class_loader) {
+ mirror::ClassLoader* class_loader) {
size_t hash = Hash(descriptor);
{
ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
@@ -3415,26 +3413,17 @@
}
mirror::Class* ClassLinker::LookupClassFromTableLocked(const char* descriptor,
- const mirror::ClassLoader* class_loader,
+ mirror::ClassLoader* class_loader,
size_t hash) {
- auto end = class_table_.end();
- for (auto it = class_table_.lower_bound(hash); it != end && it->first == hash; ++it) {
- mirror::Class* klass = it->second.Read();
- if (klass->GetClassLoader() == class_loader && klass->DescriptorEquals(descriptor)) {
- if (kIsDebugBuild) {
- // Check for duplicates in the table.
- for (++it; it != end && it->first == hash; ++it) {
- mirror::Class* klass2 = it->second.Read();
- CHECK(!(klass2->GetClassLoader() == class_loader &&
- klass2->DescriptorEquals(descriptor)))
- << PrettyClass(klass) << " " << klass << " " << klass->GetClassLoader() << " "
- << PrettyClass(klass2) << " " << klass2 << " " << klass2->GetClassLoader();
- }
- }
- return klass;
+ auto descriptor_pair = std::make_pair(descriptor, class_loader);
+ auto it = pre_zygote_class_table_.FindWithHash(descriptor_pair, hash);
+ if (it == pre_zygote_class_table_.end()) {
+ it = class_table_.FindWithHash(descriptor_pair, hash);
+ if (it == class_table_.end()) {
+ return nullptr;
}
}
- return nullptr;
+ return it->Read();
}
static mirror::ObjectArray<mirror::DexCache>* GetImageDexCaches()
@@ -3465,12 +3454,12 @@
size_t hash = Hash(descriptor);
mirror::Class* existing = LookupClassFromTableLocked(descriptor, nullptr, hash);
if (existing != nullptr) {
- CHECK(existing == klass) << PrettyClassAndClassLoader(existing) << " != "
+ CHECK_EQ(existing, klass) << PrettyClassAndClassLoader(existing) << " != "
<< PrettyClassAndClassLoader(klass);
} else {
- class_table_.insert(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+ class_table_.Insert(GcRoot<mirror::Class>(klass));
if (log_new_class_table_roots_) {
- new_class_roots_.push_back(std::make_pair(hash, GcRoot<mirror::Class>(klass)));
+ new_class_roots_.push_back(GcRoot<mirror::Class>(klass));
}
}
}
@@ -3479,6 +3468,13 @@
dex_cache_image_class_lookup_required_ = false;
}
+void ClassLinker::MoveClassTableToPreZygote() {
+ WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
+ DCHECK(pre_zygote_class_table_.Empty());
+ pre_zygote_class_table_ = std::move(class_table_);
+ class_table_.Clear();
+}
+
mirror::Class* ClassLinker::LookupClassFromImage(const char* descriptor) {
ScopedAssertNoThreadSuspension ants(Thread::Current(), "Image class lookup");
mirror::ObjectArray<mirror::DexCache>* dex_caches = GetImageDexCaches();
@@ -3507,14 +3503,32 @@
if (dex_cache_image_class_lookup_required_) {
MoveImageClassesToClassTable();
}
- size_t hash = Hash(descriptor);
- ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
- for (auto it = class_table_.lower_bound(hash), end = class_table_.end();
- it != end && it->first == hash; ++it) {
- mirror::Class* klass = it->second.Read();
- if (klass->DescriptorEquals(descriptor)) {
- result.push_back(klass);
+ WriterMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
+ while (true) {
+ auto it = class_table_.Find(descriptor);
+ if (it == class_table_.end()) {
+ break;
}
+ result.push_back(it->Read());
+ class_table_.Erase(it);
+ }
+ for (mirror::Class* k : result) {
+ class_table_.Insert(GcRoot<mirror::Class>(k));
+ }
+ size_t pre_zygote_start = result.size();
+ // Now handle the pre zygote table.
+ // Note: This dirties the pre-zygote table but shouldn't be an issue since LookupClasses is only
+ // called from the debugger.
+ while (true) {
+ auto it = pre_zygote_class_table_.Find(descriptor);
+ if (it == pre_zygote_class_table_.end()) {
+ break;
+ }
+ result.push_back(it->Read());
+ pre_zygote_class_table_.Erase(it);
+ }
+ for (size_t i = pre_zygote_start; i < result.size(); ++i) {
+ pre_zygote_class_table_.Insert(GcRoot<mirror::Class>(result[i]));
}
}
@@ -5697,9 +5711,8 @@
std::vector<mirror::Class*> all_classes;
{
ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
- for (std::pair<const size_t, GcRoot<mirror::Class> >& it : class_table_) {
- mirror::Class* klass = it.second.Read();
- all_classes.push_back(klass);
+ for (GcRoot<mirror::Class>& it : class_table_) {
+ all_classes.push_back(it.Read());
}
}
@@ -5793,7 +5806,8 @@
MoveImageClassesToClassTable();
}
ReaderMutexLock mu(self, *Locks::classlinker_classes_lock_);
- os << "Loaded classes: " << class_table_.size() << " allocated classes\n";
+ os << "Zygote loaded classes=" << pre_zygote_class_table_.Size() << " post zygote classes="
+ << class_table_.Size() << "\n";
}
size_t ClassLinker::NumLoadedClasses() {
@@ -5801,7 +5815,8 @@
MoveImageClassesToClassTable();
}
ReaderMutexLock mu(Thread::Current(), *Locks::classlinker_classes_lock_);
- return class_table_.size();
+ // Only return non zygote classes since these are the ones which apps which care about.
+ return class_table_.Size();
}
pid_t ClassLinker::GetClassesLockOwner() {
@@ -5870,4 +5885,41 @@
return descriptor;
}
+std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& root)
+ const {
+ std::string temp;
+ return Hash(root.Read()->GetDescriptor(&temp));
+}
+
+bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& a,
+ const GcRoot<mirror::Class>& b) {
+ if (a.Read()->GetClassLoader() != b.Read()->GetClassLoader()) {
+ return false;
+ }
+ std::string temp;
+ return a.Read()->DescriptorEquals(b.Read()->GetDescriptor(&temp));
+}
+
+std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(
+ const std::pair<const char*, mirror::ClassLoader*>& element) const {
+ return Hash(element.first);
+}
+
+bool ClassLinker::ClassDescriptorHashEquals::operator()(
+ const GcRoot<mirror::Class>& a, const std::pair<const char*, mirror::ClassLoader*>& b) {
+ if (a.Read()->GetClassLoader() != b.second) {
+ return false;
+ }
+ return a.Read()->DescriptorEquals(b.first);
+}
+
+bool ClassLinker::ClassDescriptorHashEquals::operator()(const GcRoot<mirror::Class>& a,
+ const char* descriptor) {
+ return a.Read()->DescriptorEquals(descriptor);
+}
+
+std::size_t ClassLinker::ClassDescriptorHashEquals::operator()(const char* descriptor) const {
+ return Hash(descriptor);
+}
+
} // namespace art