Use HashMap<> and HashSet<> in ClassLinker.
Extend the HashSet<> and HashMap<> API with constructors
that allow using a stack-allocated initial buffer to avoid
the allocation overhead for small containers.
Fix HashMap<> implementation for std::pair<> being used
as the Key. Make Signature copy-assignable so that we can
use it as (part of) a Value in HashMap<>.
Move the definition of ClassLinker::MethodTranslation from
class_linker.h to class_linker.cc. Add a default constructor
used for creating empty entries in HashMap<>.
Use HashMap<> and HashSet<> in ClassLinker instead of
std::unordered_map<> and std::unordered_set<> as it is much
faster thanks to avoiding individual nodes that need malloc
and free and for small containers we also avoid allocations
thanks to the extended HashSet<> and HashMap<> API.
Also avoid unnecessary std::vector<> for FillIfTable() and
replace linear search with HashSet<> lookup (note that the
`ContainsElement()` helper has an overload for std::set<>
but not for any other associative container).
Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Test: boots.
Bug: 175869411
Change-Id: I48722fb3bb7780bf12fb71c7449494e097e4a368
diff --git a/runtime/class_linker.cc b/runtime/class_linker.cc
index 7595699..9003bc0 100644
--- a/runtime/class_linker.cc
+++ b/runtime/class_linker.cc
@@ -28,7 +28,6 @@
#include <string>
#include <string_view>
#include <tuple>
-#include <unordered_map>
#include <utility>
#include <vector>
@@ -40,6 +39,8 @@
#include "base/arena_allocator.h"
#include "base/casts.h"
#include "base/file_utils.h"
+#include "base/hash_map.h"
+#include "base/hash_set.h"
#include "base/leb128.h"
#include "base/logging.h"
#include "base/mutex-inl.h"
@@ -6216,6 +6217,81 @@
return true;
}
+// A wrapper class representing the result of a method translation used for linking methods and
+// updating superclass default methods. For each method in a classes vtable there are 4 states it
+// could be in:
+// 1) No translation is necessary. In this case there is no MethodTranslation object for it. This
+// is the standard case and is true when the method is not overridable by a default method,
+// the class defines a concrete implementation of the method, the default method implementation
+// remains the same, or an abstract method stayed abstract.
+// 2) The method must be translated to a different default method. We note this with
+// CreateTranslatedMethod.
+// 3) The method must be replaced with a conflict method. This happens when a superclass
+// implements an interface with a default method and this class implements an unrelated
+// interface that also defines that default method. We note this with CreateConflictingMethod.
+// 4) The method must be replaced with an abstract miranda method. This happens when a superclass
+// implements an interface with a default method and this class implements a subinterface of
+// the superclass's interface which declares the default method abstract. We note this with
+// CreateAbstractMethod.
+//
+// When a method translation is unnecessary (case #1), we don't put it into the
+// default_translation maps. So an instance of MethodTranslation must be in one of #2-#4.
+class ClassLinker::MethodTranslation {
+ public:
+ MethodTranslation() : translation_(nullptr), type_(Type::kInvalid) {}
+
+ // This slot must become a default conflict method.
+ static MethodTranslation CreateConflictingMethod() {
+ return MethodTranslation(Type::kConflict, /*translation=*/nullptr);
+ }
+
+ // This slot must become an abstract method.
+ static MethodTranslation CreateAbstractMethod() {
+ return MethodTranslation(Type::kAbstract, /*translation=*/nullptr);
+ }
+
+ // Use the given method as the current value for this vtable slot during translation.
+ static MethodTranslation CreateTranslatedMethod(ArtMethod* new_method) {
+ return MethodTranslation(Type::kTranslation, new_method);
+ }
+
+ // Returns true if this is a method that must become a conflict method.
+ bool IsInConflict() const {
+ return type_ == Type::kConflict;
+ }
+
+ // Returns true if this is a method that must become an abstract method.
+ bool IsAbstract() const {
+ return type_ == Type::kAbstract;
+ }
+
+ // Returns true if this is a method that must become a different method.
+ bool IsTranslation() const {
+ return type_ == Type::kTranslation;
+ }
+
+ // Get the translated version of this method.
+ ArtMethod* GetTranslation() const {
+ DCHECK(IsTranslation());
+ DCHECK(translation_ != nullptr);
+ return translation_;
+ }
+
+ private:
+ enum class Type {
+ kInvalid,
+ kTranslation,
+ kConflict,
+ kAbstract,
+ };
+
+ MethodTranslation(Type type, ArtMethod* translation)
+ : translation_(translation), type_(type) {}
+
+ ArtMethod* translation_;
+ Type type_;
+};
+
// Populate the class vtable and itable. Compute return type indices.
bool ClassLinker::LinkMethods(Thread* self,
Handle<mirror::Class> klass,
@@ -6226,7 +6302,9 @@
// A map from vtable indexes to the method they need to be updated to point to. Used because we
// need to have default methods be in the virtuals array of each class but we don't set that up
// until LinkInterfaceMethods.
- std::unordered_map<size_t, ClassLinker::MethodTranslation> default_translations;
+ constexpr size_t kBufferSize = 8; // Avoid malloc/free for a few translations.
+ std::pair<size_t, ClassLinker::MethodTranslation> buffer[kBufferSize];
+ HashMap<size_t, ClassLinker::MethodTranslation> default_translations(buffer, kBufferSize);
// Link virtual methods then interface methods.
// We set up the interface lookup table first because we need it to determine if we need to update
// any vtable entries with new default method implementations.
@@ -6359,7 +6437,7 @@
bool ClassLinker::LinkVirtualMethods(
Thread* self,
Handle<mirror::Class> klass,
- /*out*/std::unordered_map<size_t, ClassLinker::MethodTranslation>* default_translations) {
+ /*out*/HashMap<size_t, ClassLinker::MethodTranslation>* default_translations) {
const size_t num_virtual_methods = klass->NumVirtualMethods();
if (klass->IsInterface()) {
// No vtable.
@@ -7058,7 +7136,7 @@
// Simple helper function that checks that no subtypes of 'val' are contained within the 'classes'
// set.
static bool NotSubinterfaceOfAny(
- const std::unordered_set<ObjPtr<mirror::Class>, HashObjPtr>& classes,
+ const HashSet<mirror::Class*>& classes,
ObjPtr<mirror::Class> val)
REQUIRES(Roles::uninterruptible_)
REQUIRES_SHARED(Locks::mutator_lock_) {
@@ -7090,22 +7168,32 @@
// super_ifcount entries filled in with the transitive closure of the interfaces of the superclass.
// The other entries are uninitialized. We will fill in the remaining entries in this function. The
// iftable must be large enough to hold all interfaces without changing its size.
-static size_t FillIfTable(ObjPtr<mirror::IfTable> iftable,
+static size_t FillIfTable(Thread* self,
+ ObjPtr<mirror::Class> klass,
+ ObjPtr<mirror::ObjectArray<mirror::Class>> interfaces,
+ ObjPtr<mirror::IfTable> iftable,
size_t super_ifcount,
- const std::vector<ObjPtr<mirror::Class>>& to_process)
- REQUIRES(Roles::uninterruptible_)
+ size_t num_interfaces)
REQUIRES_SHARED(Locks::mutator_lock_) {
- // This is the set of all class's already in the iftable. Used to make checking if a class has
- // already been added quicker.
- std::unordered_set<ObjPtr<mirror::Class>, HashObjPtr> classes_in_iftable;
+ ScopedAssertNoThreadSuspension nts(__FUNCTION__);
+ // This is the set of all classes already in the iftable. Used to make checking
+ // if a class has already been added quicker.
+ constexpr size_t kBufferSize = 32; // 256 bytes on 64-bit architectures.
+ mirror::Class* buffer[kBufferSize];
+ HashSet<mirror::Class*> classes_in_iftable(buffer, kBufferSize);
// The first super_ifcount elements are from the superclass. We note that they are already added.
for (size_t i = 0; i < super_ifcount; i++) {
ObjPtr<mirror::Class> iface = iftable->GetInterface(i);
DCHECK(NotSubinterfaceOfAny(classes_in_iftable, iface)) << "Bad ordering.";
- classes_in_iftable.insert(iface);
+ classes_in_iftable.insert(iface.Ptr());
}
size_t filled_ifcount = super_ifcount;
- for (ObjPtr<mirror::Class> interface : to_process) {
+ const bool have_interfaces = interfaces != nullptr;
+ for (size_t i = 0; i != num_interfaces; ++i) {
+ ObjPtr<mirror::Class> interface = have_interfaces
+ ? interfaces->Get(i)
+ : mirror::Class::GetDirectInterface(self, klass, i);
+
// Let us call the first filled_ifcount elements of iftable the current-iface-list.
// At this point in the loop current-iface-list has the invariant that:
// for every pair of interfaces I,J within it:
@@ -7113,7 +7201,7 @@
// If we have already seen this element then all of its super-interfaces must already be in the
// current-iface-list so we can skip adding it.
- if (!ContainsElement(classes_in_iftable, interface)) {
+ if (classes_in_iftable.find(interface.Ptr()) == classes_in_iftable.end()) {
// We haven't seen this interface so add all of its super-interfaces onto the
// current-iface-list, skipping those already on it.
int32_t ifcount = interface->GetIfTableCount();
@@ -7121,14 +7209,14 @@
ObjPtr<mirror::Class> super_interface = interface->GetIfTable()->GetInterface(j);
if (!ContainsElement(classes_in_iftable, super_interface)) {
DCHECK(NotSubinterfaceOfAny(classes_in_iftable, super_interface)) << "Bad ordering.";
- classes_in_iftable.insert(super_interface);
+ classes_in_iftable.insert(super_interface.Ptr());
iftable->SetInterface(filled_ifcount, super_interface);
filled_ifcount++;
}
}
DCHECK(NotSubinterfaceOfAny(classes_in_iftable, interface)) << "Bad ordering";
// Place this interface onto the current-iface-list after all of its super-interfaces.
- classes_in_iftable.insert(interface);
+ classes_in_iftable.insert(interface.Ptr());
iftable->SetInterface(filled_ifcount, interface);
filled_ifcount++;
} else if (kIsDebugBuild) {
@@ -7160,7 +7248,8 @@
return filled_ifcount;
}
-bool ClassLinker::SetupInterfaceLookupTable(Thread* self, Handle<mirror::Class> klass,
+bool ClassLinker::SetupInterfaceLookupTable(Thread* self,
+ Handle<mirror::Class> klass,
Handle<mirror::ObjectArray<mirror::Class>> interfaces) {
StackHandleScope<1> hs(self);
const bool has_superclass = klass->HasSuperClass();
@@ -7229,18 +7318,8 @@
// doesn't really do anything.
self->AllowThreadSuspension();
- size_t new_ifcount;
- {
- ScopedAssertNoThreadSuspension nts("Copying mirror::Class*'s for FillIfTable");
- std::vector<ObjPtr<mirror::Class>> to_add;
- for (size_t i = 0; i < num_interfaces; i++) {
- ObjPtr<mirror::Class> interface = have_interfaces ? interfaces->Get(i) :
- mirror::Class::GetDirectInterface(self, klass.Get(), i);
- to_add.push_back(interface);
- }
-
- new_ifcount = FillIfTable(iftable.Get(), super_ifcount, std::move(to_add));
- }
+ const size_t new_ifcount = FillIfTable(
+ self, klass.Get(), interfaces.Get(), iftable.Get(), super_ifcount, num_interfaces);
self->AllowThreadSuspension();
@@ -7378,7 +7457,7 @@
return BaseHashType::HashCombine(BaseHashType::HashCombine(0, key.first), key.second);
}
};
- std::unordered_map<PairType, int32_t, PairHash> seen;
+ HashMap<PairType, int32_t, DefaultMapEmptyFn<PairType, int32_t>, PairHash> seen;
seen.reserve(2 * num_entries);
bool need_slow_path = false;
bool found_dup = false;
@@ -7404,7 +7483,7 @@
log_fn(it->second, i);
}
} else {
- seen.emplace(pair, i);
+ seen.insert(std::make_pair(pair, i));
}
}
return std::make_pair(need_slow_path, found_dup);
@@ -7425,16 +7504,19 @@
Signature signature = Signature::NoSignature();
uint32_t name_len = 0;
+ Entry() = default;
+ Entry(const Entry& other) = default;
+ Entry& operator=(const Entry& other) = default;
+
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;
+ return name_len == other.name_len &&
+ memcmp(name, other.name, name_len) == 0 &&
+ signature == other.signature;
}
};
struct EntryHash {
@@ -7442,7 +7524,7 @@
return key.cached_hash;
}
};
- std::unordered_map<Entry, int32_t, EntryHash> map;
+ HashMap<Entry, int32_t, DefaultMapEmptyFn<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.
@@ -7468,7 +7550,7 @@
if (it != map.end()) {
log_fn(it->second, i);
} else {
- map.emplace(e, i);
+ map.insert(std::make_pair(e, i));
}
}
}
@@ -7565,7 +7647,7 @@
void ReallocMethods() REQUIRES_SHARED(Locks::mutator_lock_);
ObjPtr<mirror::PointerArray> UpdateVtable(
- const std::unordered_map<size_t, ClassLinker::MethodTranslation>& default_translations,
+ const HashMap<size_t, ClassLinker::MethodTranslation>& default_translations,
Handle<mirror::PointerArray> old_vtable) REQUIRES_SHARED(Locks::mutator_lock_);
void UpdateIfTable(Handle<mirror::IfTable> iftable) REQUIRES_SHARED(Locks::mutator_lock_);
@@ -7893,7 +7975,7 @@
}
ObjPtr<mirror::PointerArray> ClassLinker::LinkInterfaceMethodsHelper::UpdateVtable(
- const std::unordered_map<size_t, ClassLinker::MethodTranslation>& default_translations,
+ const HashMap<size_t, ClassLinker::MethodTranslation>& default_translations,
Handle<mirror::PointerArray> old_vtable) {
// Update the vtable to the new method structures. We can skip this for interfaces since they
// do not have vtables.
@@ -8018,7 +8100,7 @@
bool ClassLinker::LinkInterfaceMethods(
Thread* self,
Handle<mirror::Class> klass,
- const std::unordered_map<size_t, ClassLinker::MethodTranslation>& default_translations,
+ const HashMap<size_t, ClassLinker::MethodTranslation>& default_translations,
bool* out_new_conflict,
ArtMethod** out_imt) {
StackHandleScope<3> hs(self);