ART: Find and cache indices for method names
Cache the range of string indices starting with '<,' especially the
well-defined "<clinit>" and "<init>," to optimize the constructor-flags
check.
Saves about .2% of instructions.
Bug: 78568168
Test: m test-art-host
Change-Id: I9ed26bb0382a169d945bcec4067c0166c200e227
diff --git a/libdexfile/dex/dex_file_verifier.cc b/libdexfile/dex/dex_file_verifier.cc
index 5f7b4e8..2380f48 100644
--- a/libdexfile/dex/dex_file_verifier.cc
+++ b/libdexfile/dex/dex_file_verifier.cc
@@ -18,7 +18,6 @@
#include <inttypes.h>
-#include <limits>
#include <memory>
#include "android-base/stringprintf.h"
@@ -106,66 +105,6 @@
return dex_file_->StringDataByIdx(idx);
}
-// Try to find the name of the method with the given index. We do not want to rely on DexFile
-// infrastructure at this point, so do it all by hand. begin and header correspond to begin_ and
-// header_ of the DexFileVerifier. str will contain the pointer to the method name on success
-// (flagged by the return value), otherwise error_msg will contain an error string.
-static bool FindMethodName(uint32_t method_index,
- const uint8_t* begin,
- const DexFile::Header* header,
- const char** str,
- std::string* error_msg) {
- if (method_index >= header->method_ids_size_) {
- *error_msg = "Method index not available for method flags verification";
- return false;
- }
- uint32_t string_idx =
- (reinterpret_cast<const DexFile::MethodId*>(begin + header->method_ids_off_) +
- method_index)->name_idx_.index_;
- if (string_idx >= header->string_ids_size_) {
- *error_msg = "String index not available for method flags verification";
- return false;
- }
- uint32_t string_off =
- (reinterpret_cast<const DexFile::StringId*>(begin + header->string_ids_off_) + string_idx)->
- string_data_off_;
- if (string_off >= header->file_size_) {
- *error_msg = "String offset out of bounds for method flags verification";
- return false;
- }
- const uint8_t* str_data_ptr = begin + string_off;
- uint32_t dummy;
- if (!DecodeUnsignedLeb128Checked(&str_data_ptr, begin + header->file_size_, &dummy)) {
- *error_msg = "String size out of bounds for method flags verification";
- return false;
- }
- *str = reinterpret_cast<const char*>(str_data_ptr);
- return true;
-}
-
-// Gets constructor flags based on the |method_name|. Returns true if
-// method_name is either <clinit> or <init> and sets
-// |constructor_flags_by_name| appropriately. Otherwise set
-// |constructor_flags_by_name| to zero and returns whether
-// |method_name| is valid.
-bool GetConstructorFlagsForMethodName(const char* method_name,
- uint32_t* constructor_flags_by_name) {
- if (method_name[0] != '<') {
- *constructor_flags_by_name = 0;
- return true;
- }
- if (strcmp(method_name + 1, "clinit>") == 0) {
- *constructor_flags_by_name = kAccStatic | kAccConstructor;
- return true;
- }
- if (strcmp(method_name + 1, "init>") == 0) {
- *constructor_flags_by_name = kAccConstructor;
- return true;
- }
- *constructor_flags_by_name = 0;
- return false;
-}
-
const char* DexFileVerifier::CheckLoadStringByTypeIdx(dex::TypeIndex type_idx,
const char* error_string) {
if (UNLIKELY(!CheckIndex(type_idx.index_, dex_file_->NumTypeIds(), error_string))) {
@@ -682,10 +621,11 @@
return false;
}
+ const DexFile::MethodId& method_id =
+ *(reinterpret_cast<const DexFile::MethodId*>(begin_ + header_->method_ids_off_) + idx);
+
// Check that it's the right class.
- dex::TypeIndex my_class_index =
- (reinterpret_cast<const DexFile::MethodId*>(begin_ + header_->method_ids_off_) + idx)->
- class_idx_;
+ dex::TypeIndex my_class_index = method_id.class_idx_;
if (class_type_index != my_class_index) {
ErrorStringPrintf("Method's class index unexpected, %" PRIu16 " vs %" PRIu16,
my_class_index.index_,
@@ -710,16 +650,23 @@
}
std::string error_msg;
- const char* method_name;
- if (!FindMethodName(idx, begin_, header_, &method_name, &error_msg)) {
- ErrorStringPrintf("%s", error_msg.c_str());
- return false;
- }
-
uint32_t constructor_flags_by_name = 0;
- if (!GetConstructorFlagsForMethodName(method_name, &constructor_flags_by_name)) {
- ErrorStringPrintf("Bad method name: %s", method_name);
- return false;
+ {
+ uint32_t string_idx = method_id.name_idx_.index_;
+ if (!CheckIndex(string_idx, header_->string_ids_size_, "method flags verification")) {
+ return false;
+ }
+ if (UNLIKELY(string_idx < angle_bracket_end_index_) &&
+ string_idx >= angle_bracket_start_index_) {
+ if (string_idx == angle_clinit_angle_index_) {
+ constructor_flags_by_name = kAccStatic | kAccConstructor;
+ } else if (string_idx == angle_init_angle_index_) {
+ constructor_flags_by_name = kAccConstructor;
+ } else {
+ ErrorStringPrintf("Bad method name for method index %u", idx);
+ return false;
+ }
+ }
}
bool has_code = (code_offset != 0);
@@ -1961,6 +1908,10 @@
return false;
}
+ if (type == DexFile::kDexTypeClassDataItem) {
+ FindStringRangesForMethodNames();
+ }
+
// Check each item based on its type.
switch (type) {
case DexFile::kDexTypeHeaderItem:
@@ -3181,6 +3132,55 @@
return true;
}
+void DexFileVerifier::FindStringRangesForMethodNames() {
+ // Use DexFile::StringId* as RandomAccessIterator.
+ const DexFile::StringId* first = reinterpret_cast<const DexFile::StringId*>(
+ begin_ + header_->string_ids_off_);
+ const DexFile::StringId* last = first + header_->string_ids_size_;
+
+ auto get_string = [begin = begin_](const DexFile::StringId& id) {
+ const uint8_t* str_data_ptr = begin + id.string_data_off_;
+ DecodeUnsignedLeb128(&str_data_ptr);
+ return reinterpret_cast<const char*>(str_data_ptr);
+ };
+ auto compare = [&get_string](const DexFile::StringId& lhs, const char* rhs) {
+ return strcmp(get_string(lhs), rhs) < 0;
+ };
+
+ // '=' follows '<'
+ static_assert('<' + 1 == '=', "Unexpected character relation");
+ const auto angle_end = std::lower_bound(first, last, "=", compare);
+ angle_bracket_end_index_ = angle_end - first;
+
+ const auto angle_start = std::lower_bound(first, angle_end, "<", compare);
+ angle_bracket_start_index_ = angle_start - first;
+ if (angle_start == angle_end) {
+ // No strings starting with '<'.
+ angle_init_angle_index_ = std::numeric_limits<size_t>::max();
+ angle_clinit_angle_index_ = std::numeric_limits<size_t>::max();
+ return;
+ }
+
+ {
+ constexpr const char* kClinit = "<clinit>";
+ const auto it = std::lower_bound(angle_start, angle_end, kClinit, compare);
+ if (it != angle_end && strcmp(get_string(*it), kClinit) == 0) {
+ angle_clinit_angle_index_ = it - first;
+ } else {
+ angle_clinit_angle_index_ = std::numeric_limits<size_t>::max();
+ }
+ }
+ {
+ constexpr const char* kInit = "<init>";
+ const auto it = std::lower_bound(angle_start, angle_end, kInit, compare);
+ if (it != angle_end && strcmp(get_string(*it), kInit) == 0) {
+ angle_init_angle_index_ = it - first;
+ } else {
+ angle_init_angle_index_ = std::numeric_limits<size_t>::max();
+ }
+ }
+}
+
bool DexFileVerifier::CheckMethodAccessFlags(uint32_t method_index,
uint32_t method_access_flags,
uint32_t class_access_flags,
diff --git a/libdexfile/dex/dex_file_verifier.h b/libdexfile/dex/dex_file_verifier.h
index a4c23bb..eaffc62 100644
--- a/libdexfile/dex/dex_file_verifier.h
+++ b/libdexfile/dex/dex_file_verifier.h
@@ -17,6 +17,7 @@
#ifndef ART_LIBDEXFILE_DEX_DEX_FILE_VERIFIER_H_
#define ART_LIBDEXFILE_DEX_DEX_FILE_VERIFIER_H_
+#include <limits>
#include <unordered_set>
#include "base/hash_map.h"
@@ -52,7 +53,11 @@
verify_checksum_(verify_checksum),
header_(&dex_file->GetHeader()),
ptr_(nullptr),
- previous_item_(nullptr) {
+ previous_item_(nullptr),
+ angle_bracket_start_index_(std::numeric_limits<size_t>::max()),
+ angle_bracket_end_index_(std::numeric_limits<size_t>::max()),
+ angle_init_angle_index_(std::numeric_limits<size_t>::max()),
+ angle_clinit_angle_index_(std::numeric_limits<size_t>::max()) {
}
bool Verify();
@@ -195,6 +200,8 @@
// Check validity of given method if it's a constructor or class initializer.
bool CheckConstructorProperties(uint32_t method_index, uint32_t constructor_flags);
+ void FindStringRangesForMethodNames();
+
const DexFile* const dex_file_;
const uint8_t* const begin_;
const size_t size_;
@@ -237,6 +244,20 @@
// Set of type ids for which there are ClassDef elements in the dex file.
std::unordered_set<decltype(DexFile::ClassDef::class_idx_)> defined_classes_;
+
+ // Cached string indices for "interesting" entries wrt/ method names. Will be populated by
+ // FindStringRangesForMethodNames (which is automatically called before verifying the
+ // classdataitem section).
+ //
+ // Strings starting with '<' are in the range
+ // [angle_bracket_start_index_,angle_bracket_end_index_).
+ // angle_init_angle_index_ and angle_clinit_angle_index_ denote the indices of "<init>" and
+ // angle_clinit_angle_index_, respectively. If any value is not found, the corresponding
+ // index will be larger than any valid string index for this dex file.
+ size_t angle_bracket_start_index_;
+ size_t angle_bracket_end_index_;
+ size_t angle_init_angle_index_;
+ size_t angle_clinit_angle_index_;
};
} // namespace art
diff --git a/libdexfile/dex/dex_file_verifier_test.cc b/libdexfile/dex/dex_file_verifier_test.cc
index 4c3cf77..f82081f 100644
--- a/libdexfile/dex/dex_file_verifier_test.cc
+++ b/libdexfile/dex/dex_file_verifier_test.cc
@@ -173,7 +173,7 @@
DexFile::MethodId* method_id = const_cast<DexFile::MethodId*>(&dex_file->GetMethodId(0));
method_id->name_idx_ = dex::StringIndex(0xFF);
},
- "String index not available for method flags verification");
+ "Bad index for method flags verification");
}
// Method flags test class generated from the following smali code. The declared-synchronized