ART: Use bitset in dex file verifier
Use a bitset instead of a hash set. The maximum memory usage is 8K,
which is reasonable and bounded.
Instruction count improvement is in the noise (a percent of a percent).
Branch misses improve by a percent.
Bug: 110852609
Test: m test-art-host
Change-Id: I8bb44ba8ab90db8ef632f2977774b389c3a504b6
diff --git a/libdexfile/dex/dex_file_verifier.cc b/libdexfile/dex/dex_file_verifier.cc
index ee4b0e6..c069307 100644
--- a/libdexfile/dex/dex_file_verifier.cc
+++ b/libdexfile/dex/dex_file_verifier.cc
@@ -21,6 +21,8 @@
#include <algorithm>
#include <memory>
+#include "android-base/logging.h"
+#include "android-base/macros.h"
#include "android-base/stringprintf.h"
#include "base/leb128.h"
@@ -2469,11 +2471,16 @@
return false;
}
// Check for duplicate class def.
- if (defined_classes_.find(item->class_idx_) != defined_classes_.end()) {
+
+ // Sanity checks, should be optimized away.
+ DCHECK_LE(item->class_idx_.index_, kTypeIdLimit);
+ static_assert(kTypeIdLimit < kTypeIdSize, "Unexpected type-id range.");
+
+ if (defined_classes_[item->class_idx_.index_]) {
ErrorStringPrintf("Redefinition of class with type idx: '%d'", item->class_idx_.index_);
return false;
}
- defined_classes_.insert(item->class_idx_);
+ defined_classes_[item->class_idx_.index_] = true;
if (UNLIKELY(!VerifyTypeDescriptor(item->class_idx_,
@@ -3015,10 +3022,6 @@
const dex::MapItem* item = map->list_;
uint32_t count = map->size_;
- // Avoid allocations, reserve space ahead of time. At most the type-id limit number
- // of type IDs can be added.
- defined_classes_.reserve(std::min(header_->class_defs_size_, kTypeIdLimit) + 1);
-
// Cross check the items listed in the map.
for (; count != 0u; --count) {
uint32_t section_offset = item->offset_;
diff --git a/libdexfile/dex/dex_file_verifier.h b/libdexfile/dex/dex_file_verifier.h
index 737e18a..3e1583e 100644
--- a/libdexfile/dex/dex_file_verifier.h
+++ b/libdexfile/dex/dex_file_verifier.h
@@ -17,10 +17,10 @@
#ifndef ART_LIBDEXFILE_DEX_DEX_FILE_VERIFIER_H_
#define ART_LIBDEXFILE_DEX_DEX_FILE_VERIFIER_H_
+#include <bitset>
#include <limits>
#include "base/hash_map.h"
-#include "base/hash_set.h"
#include "base/safe_map.h"
#include "class_accessor.h"
#include "dex_file.h"
@@ -252,9 +252,6 @@
std::string failure_reason_;
- // Set of type ids for which there are ClassDef elements in the dex file.
- HashSet<decltype(dex::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).
@@ -272,6 +269,12 @@
// A bitvector for verified type descriptors. Each bit corresponds to a type index. A set
// bit denotes that the descriptor has been verified wrt/ IsValidDescriptor.
std::vector<char> verified_type_descriptors_;
+
+ // Set of type ids for which there are ClassDef elements in the dex file. Using a bitset
+ // avoids all allocations. The bitset should be implemented as 8K of storage, which is
+ // tight enough for all callers.
+ static constexpr size_t kTypeIdSize = 65536u;
+ std::bitset<kTypeIdSize> defined_classes_;
};
} // namespace art