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