Binary search for method by name string and signature.
Start with a binary search for the name string and when
successful, compare the signature. On mismatch, repeat the
search with the found name index instead of the name string
until we fail to find the name, have a signature match or
end up with a method range with the same name index and
finish with a simple binary search for the signature.
Make this search sufficiently generic so that the code can
be easily reused for fields in the future.
Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 181943478
Change-Id: I19b4779c019e9991b6d02ace57e378c029ba1174
diff --git a/libdexfile/dex/dex_file-inl.h b/libdexfile/dex/dex_file-inl.h
index 8b9e342..d9c5211 100644
--- a/libdexfile/dex/dex_file-inl.h
+++ b/libdexfile/dex/dex_file-inl.h
@@ -193,6 +193,15 @@
return StringDataByIdx(proto_id.shorty_idx_);
}
+ALWAYS_INLINE
+inline std::string_view DexFile::GetShortyView(const dex::ProtoId& proto_id) const {
+ uint32_t lhs_shorty_len;
+ const char* lhs_shorty_data =
+ StringDataAndUtf16LengthByIdx(proto_id.shorty_idx_, &lhs_shorty_len);
+ DCHECK_EQ(lhs_shorty_data[lhs_shorty_len], '\0'); // For a shorty utf16 length == mutf8 length.
+ return std::string_view(lhs_shorty_data, lhs_shorty_len);
+}
+
inline const dex::TryItem* DexFile::GetTryItems(const DexInstructionIterator& code_item_end,
uint32_t offset) {
return reinterpret_cast<const dex::TryItem*>
diff --git a/libdexfile/dex/dex_file.h b/libdexfile/dex/dex_file.h
index c2a2d64..02e0015 100644
--- a/libdexfile/dex/dex_file.h
+++ b/libdexfile/dex/dex_file.h
@@ -510,6 +510,7 @@
// Returns the short form method descriptor for the given prototype.
const char* GetShorty(dex::ProtoIndex proto_idx) const;
+ std::string_view GetShortyView(const dex::ProtoId& proto_id) const;
const dex::TypeList* GetProtoParameters(const dex::ProtoId& proto_id) const {
return DataPointer<dex::TypeList>(proto_id.parameters_off_);
diff --git a/libdexfile/dex/signature-inl.h b/libdexfile/dex/signature-inl.h
index 12ad1b3..f2760c3 100644
--- a/libdexfile/dex/signature-inl.h
+++ b/libdexfile/dex/signature-inl.h
@@ -33,19 +33,9 @@
if (dex_file_ == rhs.dex_file_) {
return proto_id_ == rhs.proto_id_;
}
- uint32_t lhs_shorty_len; // For a shorty utf16 length == mutf8 length.
- const char* lhs_shorty_data = dex_file_->StringDataAndUtf16LengthByIdx(proto_id_->shorty_idx_,
- &lhs_shorty_len);
- std::string_view lhs_shorty(lhs_shorty_data, lhs_shorty_len);
- {
- uint32_t rhs_shorty_len;
- const char* rhs_shorty_data =
- rhs.dex_file_->StringDataAndUtf16LengthByIdx(rhs.proto_id_->shorty_idx_,
- &rhs_shorty_len);
- std::string_view rhs_shorty(rhs_shorty_data, rhs_shorty_len);
- if (lhs_shorty != rhs_shorty) {
- return false; // Shorty mismatch.
- }
+ std::string_view lhs_shorty = dex_file_->GetShortyView(*proto_id_);
+ if (lhs_shorty != rhs.dex_file_->GetShortyView(*rhs.proto_id_)) {
+ return false; // Shorty mismatch.
}
if (lhs_shorty[0] == 'L') {
const dex::TypeId& return_type_id = dex_file_->GetTypeId(proto_id_->return_type_idx_);
@@ -57,18 +47,19 @@
}
}
if (lhs_shorty.find('L', 1) != std::string_view::npos) {
- const dex::TypeList* params = dex_file_->GetProtoParameters(*proto_id_);
+ const dex::TypeList* lhs_params = dex_file_->GetProtoParameters(*proto_id_);
const dex::TypeList* rhs_params = rhs.dex_file_->GetProtoParameters(*rhs.proto_id_);
// We found a reference parameter in the matching shorty, so both lists must be non-empty.
- DCHECK(params != nullptr);
+ DCHECK(lhs_params != nullptr);
DCHECK(rhs_params != nullptr);
- uint32_t params_size = params->Size();
- DCHECK_EQ(params_size, rhs_params->Size()); // Parameter list size must match.
+ uint32_t params_size = lhs_shorty.size() - 1u;
+ DCHECK_EQ(params_size, lhs_params->Size()); // Parameter list sizes must match shorty.
+ DCHECK_EQ(params_size, rhs_params->Size());
for (uint32_t i = 0; i < params_size; ++i) {
- const dex::TypeId& param_id = dex_file_->GetTypeId(params->GetTypeItem(i).type_idx_);
+ const dex::TypeId& lhs_param_id = dex_file_->GetTypeId(lhs_params->GetTypeItem(i).type_idx_);
const dex::TypeId& rhs_param_id =
rhs.dex_file_->GetTypeId(rhs_params->GetTypeItem(i).type_idx_);
- if (!DexFile::StringEquals(dex_file_, param_id.descriptor_idx_,
+ if (!DexFile::StringEquals(dex_file_, lhs_param_id.descriptor_idx_,
rhs.dex_file_, rhs_param_id.descriptor_idx_)) {
return false; // Parameter type mismatch.
}
@@ -77,6 +68,61 @@
return true;
}
+inline int Signature::Compare(const Signature& rhs) const {
+ DCHECK(dex_file_ != nullptr);
+ DCHECK(rhs.dex_file_ != nullptr);
+ if (dex_file_ == rhs.dex_file_) {
+ return static_cast<int>(dex_file_->GetIndexForProtoId(*proto_id_).index_) -
+ static_cast<int>(rhs.dex_file_->GetIndexForProtoId(*rhs.proto_id_).index_);
+ }
+ // Use shorty to avoid looking at primitive type descriptors
+ // as long as they are not compared with reference descriptors.
+ std::string_view lhs_shorty = dex_file_->GetShortyView(*proto_id_);
+ std::string_view rhs_shorty = rhs.dex_file_->GetShortyView(*rhs.proto_id_);
+ // Note that 'L' in a shorty can represent an array type starting with '[',
+ // so do the full type descriptor comparison when we see 'L' in either shorty.
+ if (lhs_shorty[0] == 'L' || rhs_shorty[0] == 'L') {
+ std::string_view lhs_return_type = dex_file_->GetTypeDescriptorView(
+ dex_file_->GetTypeId(proto_id_->return_type_idx_));
+ std::string_view rhs_return_type = rhs.dex_file_->GetTypeDescriptorView(
+ rhs.dex_file_->GetTypeId(rhs.proto_id_->return_type_idx_));
+ int cmp_result = lhs_return_type.compare(rhs_return_type);
+ if (cmp_result != 0) {
+ return cmp_result;
+ }
+ } else if (lhs_shorty[0] != rhs_shorty[0]) {
+ return static_cast<int>(lhs_shorty[0]) - static_cast<int>(rhs_shorty[0]);
+ }
+ size_t min_shorty_size = std::min(lhs_shorty.size(), rhs_shorty.size());
+ if (min_shorty_size != 1u) { // If both shortys contain parameters, compare parameters.
+ const dex::TypeList* lhs_params = dex_file_->GetProtoParameters(*proto_id_);
+ const dex::TypeList* rhs_params = rhs.dex_file_->GetProtoParameters(*rhs.proto_id_);
+ DCHECK(lhs_params != nullptr);
+ DCHECK(rhs_params != nullptr);
+ for (size_t i = 1u; i != min_shorty_size; ++i) {
+ if (lhs_shorty[i] == 'L' || rhs_shorty[i] == 'L') {
+ std::string_view lhs_param_type = dex_file_->GetTypeDescriptorView(
+ dex_file_->GetTypeId(lhs_params->GetTypeItem(i - 1u).type_idx_));
+ std::string_view rhs_param_type = rhs.dex_file_->GetTypeDescriptorView(
+ rhs.dex_file_->GetTypeId(rhs_params->GetTypeItem(i - 1u).type_idx_));
+ int cmp_result = lhs_param_type.compare(rhs_param_type);
+ if (cmp_result != 0) {
+ return cmp_result;
+ }
+ } else if (lhs_shorty[i] != rhs_shorty[i]) {
+ return static_cast<int>(lhs_shorty[i]) - static_cast<int>(rhs_shorty[i]);
+ }
+ }
+ }
+ if (lhs_shorty.size() == rhs_shorty.size()) {
+ return 0;
+ } else if (lhs_shorty.size() < rhs_shorty.size()) {
+ return -1;
+ } else {
+ return 1;
+ }
+}
+
} // namespace art
#endif // ART_LIBDEXFILE_DEX_SIGNATURE_INL_H_
diff --git a/libdexfile/dex/signature.h b/libdexfile/dex/signature.h
index 232819b..62def74 100644
--- a/libdexfile/dex/signature.h
+++ b/libdexfile/dex/signature.h
@@ -51,6 +51,13 @@
bool operator==(std::string_view rhs) const;
+ // Three-way compare.
+ // Return a value >0 if `rhs` is higher than `*this`, <0 if lower and 0 if equal.
+ //
+ // The order is the same as the `ProtoId` order required by dex file specification if both
+ // signatures were in the same dex file.
+ int Compare(const Signature& rhs) const;
+
private:
Signature(const DexFile* dex, const dex::ProtoId& proto) : dex_file_(dex), proto_id_(&proto) {
}
diff --git a/runtime/mirror/class.cc b/runtime/mirror/class.cc
index e6542bc..3a4e882 100644
--- a/runtime/mirror/class.cc
+++ b/runtime/mirror/class.cc
@@ -689,6 +689,152 @@
return FindClassMethodWithSignature(this, name, signature, pointer_size);
}
+// Binary search a range with a three-way compare function.
+//
+// Return a tuple consisting of a `success` value, the index of the match (`mid`) and
+// the remaining range when we found the match (`begin` and `end`). This is useful for
+// subsequent binary search with a secondary comparator, see `ClassMemberBinarySearch()`.
+template <typename Compare>
+ALWAYS_INLINE
+std::tuple<bool, uint32_t, uint32_t, uint32_t> BinarySearch(uint32_t begin,
+ uint32_t end,
+ Compare&& cmp)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ while (begin != end) {
+ uint32_t mid = (begin + end) >> 1;
+ auto cmp_result = cmp(mid);
+ if (cmp_result == 0) {
+ return {true, mid, begin, end};
+ }
+ if (cmp_result > 0) {
+ begin = mid + 1u;
+ } else {
+ end = mid;
+ }
+ }
+ return {false, 0u, 0u, 0u};
+}
+
+// Binary search for class members. The range passed to this search must be sorted, so
+// declared methods or fields cannot be searched directly but declared direct methods,
+// declared virtual methods, declared static fields or declared instance fields can.
+template <typename NameCompare, typename SecondCompare, typename NameIndexGetter>
+ALWAYS_INLINE
+std::tuple<bool, uint32_t> ClassMemberBinarySearch(uint32_t begin,
+ uint32_t end,
+ NameCompare&& name_cmp,
+ SecondCompare&& second_cmp,
+ NameIndexGetter&& get_name_idx)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ // First search for the item with the given name.
+ bool success;
+ uint32_t mid;
+ std::tie(success, mid, begin, end) = BinarySearch(begin, end, name_cmp);
+ if (!success) {
+ return {false, 0u};
+ }
+ // If found, do the secondary comparison.
+ auto second_cmp_result = second_cmp(mid);
+ if (second_cmp_result == 0) {
+ return {true, mid};
+ }
+ // We have matched the name but not the secondary comparison. We no longer need to
+ // search for the name as string as we know the matching name string index.
+ // Repeat the above binary searches and secondary comparisons with a simpler name
+ // index compare until the search range contains only matching name.
+ auto name_idx = get_name_idx(mid);
+ if (second_cmp_result > 0) {
+ do {
+ begin = mid + 1u;
+ auto name_index_cmp = [&](uint32_t mid2) REQUIRES_SHARED(Locks::mutator_lock_) {
+ DCHECK_LE(name_idx, get_name_idx(mid2));
+ return (name_idx != get_name_idx(mid2)) ? -1 : 0;
+ };
+ std::tie(success, mid, begin, end) = BinarySearch(begin, end, name_index_cmp);
+ if (!success) {
+ return {false, 0u};
+ }
+ second_cmp_result = second_cmp(mid);
+ } while (second_cmp_result > 0);
+ end = mid;
+ } else {
+ do {
+ end = mid;
+ auto name_index_cmp = [&](uint32_t mid2) REQUIRES_SHARED(Locks::mutator_lock_) {
+ DCHECK_GE(name_idx, get_name_idx(mid2));
+ return (name_idx != get_name_idx(mid2)) ? 1 : 0;
+ };
+ std::tie(success, mid, begin, end) = BinarySearch(begin, end, name_index_cmp);
+ if (!success) {
+ return {false, 0u};
+ }
+ second_cmp_result = second_cmp(mid);
+ } while (second_cmp_result < 0);
+ begin = mid + 1u;
+ }
+ if (second_cmp_result == 0) {
+ return {true, mid};
+ }
+ // All items in the remaining range have a matching name, so search with secondary comparison.
+ std::tie(success, mid, std::ignore, std::ignore) = BinarySearch(begin, end, second_cmp);
+ return {success, mid};
+}
+
+static std::tuple<bool, ArtMethod*> FindDeclaredClassMethod(ObjPtr<mirror::Class> klass,
+ const DexFile& dex_file,
+ std::string_view name,
+ Signature signature,
+ PointerSize pointer_size)
+ REQUIRES_SHARED(Locks::mutator_lock_) {
+ DCHECK(&klass->GetDexFile() == &dex_file);
+ DCHECK(!name.empty());
+
+ ArraySlice<ArtMethod> declared_methods = klass->GetDeclaredMethodsSlice(pointer_size);
+ DCHECK(!declared_methods.empty());
+ auto get_method_id = [&](uint32_t mid) REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE
+ -> const dex::MethodId& {
+ ArtMethod& method = declared_methods[mid];
+ DCHECK(method.GetDexFile() == &dex_file);
+ DCHECK_NE(method.GetDexMethodIndex(), dex::kDexNoIndex);
+ return dex_file.GetMethodId(method.GetDexMethodIndex());
+ };
+ auto name_cmp = [&](uint32_t mid) REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
+ // Do not use ArtMethod::GetNameView() to avoid reloading dex file through the same
+ // declaring class from different methods and also avoid the runtime method check.
+ const dex::MethodId& method_id = get_method_id(mid);
+ return name.compare(dex_file.GetMethodNameView(method_id));
+ };
+ auto signature_cmp = [&](uint32_t mid) REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
+ // Do not use ArtMethod::GetSignature() to avoid reloading dex file through the same
+ // declaring class from different methods and also avoid the runtime method check.
+ const dex::MethodId& method_id = get_method_id(mid);
+ return signature.Compare(dex_file.GetMethodSignature(method_id));
+ };
+ auto get_name_idx = [&](uint32_t mid) REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
+ const dex::MethodId& method_id = get_method_id(mid);
+ return method_id.name_idx_;
+ };
+
+ // Use binary search in the sorted direct methods, then in the sorted virtual methods.
+ uint32_t num_direct_methods = klass->NumDirectMethods();
+ uint32_t num_declared_methods = dchecked_integral_cast<uint32_t>(declared_methods.size());
+ DCHECK_LE(num_direct_methods, num_declared_methods);
+ const uint32_t ranges[2][2] = {
+ {0u, num_direct_methods}, // Declared direct methods.
+ {num_direct_methods, num_declared_methods} // Declared virtual methods.
+ };
+ for (const uint32_t (&range)[2] : ranges) {
+ auto [success, mid] =
+ ClassMemberBinarySearch(range[0], range[1], name_cmp, signature_cmp, get_name_idx);
+ if (success) {
+ return {true, &declared_methods[mid]};
+ }
+ }
+
+ // Did not find a declared method in either slice.
+ return {false, nullptr};
+}
+
FLATTEN
ArtMethod* Class::FindClassMethod(ObjPtr<DexCache> dex_cache,
uint32_t dex_method_idx,
@@ -707,25 +853,22 @@
}
}
}
+
// If not found, we need to search by name and signature.
const DexFile& dex_file = *dex_cache->GetDexFile();
const dex::MethodId& method_id = dex_file.GetMethodId(dex_method_idx);
const Signature signature = dex_file.GetMethodSignature(method_id);
std::string_view name; // Do not touch the dex file string data until actually needed.
+
// If we do not have a dex_cache match, try to find the declared method in this class now.
if (this_dex_cache != dex_cache && !GetDeclaredMethodsSlice(pointer_size).empty()) {
DCHECK(name.empty());
name = dex_file.GetMethodNameView(method_id);
- const DexFile& this_dex_file = *this_dex_cache->GetDexFile();
- for (ArtMethod& method : GetDeclaredMethodsSlice(pointer_size)) {
- // Do not use ArtMethod::GetNameView() to avoid reloading dex file through the same
- // declaring class from different methods and also avoid the runtime method check.
- DCHECK(method.GetDexFile() == &this_dex_file);
- DCHECK_NE(method.GetDexMethodIndex(), dex::kDexNoIndex);
- std::string_view other_name = this_dex_file.GetMethodNameView(method.GetDexMethodIndex());
- if (other_name == name && method.GetSignature() == signature) {
- return &method;
- }
+ auto [success, method] = FindDeclaredClassMethod(
+ this, *this_dex_cache->GetDexFile(), name, signature, pointer_size);
+ DCHECK_EQ(success, method != nullptr);
+ if (success) {
+ return method;
}
}
@@ -737,7 +880,8 @@
for (; klass != nullptr; klass = klass->GetSuperClass()) {
ArtMethod* candidate_method = nullptr;
ArraySlice<ArtMethod> declared_methods = klass->GetDeclaredMethodsSlice(pointer_size);
- if (klass->GetDexCache() == dex_cache) {
+ ObjPtr<DexCache> klass_dex_cache = klass->GetDexCache();
+ if (klass_dex_cache == dex_cache) {
// Matching dex_cache. We cannot compare the `dex_method_idx` anymore because
// the type index differs, so compare the name index and proto index.
for (ArtMethod& method : declared_methods) {
@@ -752,17 +896,11 @@
if (name.empty()) {
name = dex_file.GetMethodNameView(method_id);
}
- const DexFile& other_dex_file = klass->GetDexFile();
- for (ArtMethod& method : declared_methods) {
- // Do not use ArtMethod::GetNameView() to avoid reloading dex file through the same
- // declaring class from different methods and also avoid the runtime method check.
- DCHECK(method.GetDexFile() == &other_dex_file);
- DCHECK_NE(method.GetDexMethodIndex(), dex::kDexNoIndex);
- std::string_view other_name = other_dex_file.GetMethodNameView(method.GetDexMethodIndex());
- if (other_name == name && method.GetSignature() == signature) {
- candidate_method = &method;
- break;
- }
+ auto [success, method] = FindDeclaredClassMethod(
+ klass, *klass_dex_cache->GetDexFile(), name, signature, pointer_size);
+ DCHECK_EQ(success, method != nullptr);
+ if (success) {
+ candidate_method = method;
}
}
if (candidate_method != nullptr) {