Implementation of fast lookup table to search class_def by descriptor
Lookup table is a hash table which built at compile time and stored
into oat file. At runtime the table is restored and used in the
method DexFile::FindClassDef(const char*) to perform fast search of
the class_def_idx by class descriptor. Advantages of the lookup table
over the HashSet (runtime/base/hash_set.h) are:
1. Lookup table is built at compile time and uses read-only memory at
runtime
2. Lookup table uses less memory then DexFile::Index (less by 80% for
/system/framework/framework.jar on Nexus5)
3. Lookup table does less string comparisons compared with HashSet
(less by 70% for zygote process on Nexus5)
The disadvantage of the lookup table is it increased boot.oat size by
0.2% on Nexus5 and application .oat file by 0.3% in average on Nexus5.
mathieuc changes:
Create lookup table in dex2oat to speed up compilation. Clean up code
to follow style guide and use less static functions. Added
performance measurements.
Compile ~100 APKs 5 times with filter interpret-only:
Before:
real 1m8.989s
user 0m59.318s
sys 0m7.773s
After:
real 1m1.493s
user 0m52.055s
sys 0m7.581s
App launch (AOSP N5 maps, average of 45 runs):
Before: 966.84ms
After: 923.733ms
Launch speedup is 4.7%
Memory usage compared to HashSet index on 50 various APK:
32 bit: HashSet ~625694b vs TypeLookupTable ~404268b
64 bit: HashSet ~1251390b vs TypeLookupTable ~404268b
Bug: 10921004
Bug: 20269715
Change-Id: I7246c1d9ad9fe81fe5c5907a4bf70396d8f9242a
diff --git a/runtime/Android.mk b/runtime/Android.mk
index 09d7311..1fdffe3 100644
--- a/runtime/Android.mk
+++ b/runtime/Android.mk
@@ -47,6 +47,7 @@
dex_file_verifier.cc \
dex_instruction.cc \
elf_file.cc \
+ fault_handler.cc \
gc/allocation_record.cc \
gc/allocator/dlmalloc.cc \
gc/allocator/rosalloc.cc \
@@ -162,6 +163,7 @@
os_linux.cc \
parsed_options.cc \
primitive.cc \
+ profiler.cc \
quick_exception_handler.cc \
quick/inline_method_analyser.cc \
reference_table.cc \
@@ -176,8 +178,7 @@
thread_pool.cc \
trace.cc \
transaction.cc \
- profiler.cc \
- fault_handler.cc \
+ type_lookup_table.cc \
utf.cc \
utils.cc \
verifier/dex_gc_map.cc \
diff --git a/runtime/dex_file.cc b/runtime/dex_file.cc
index ae62e2b..b3ca6ac 100644
--- a/runtime/dex_file.cc
+++ b/runtime/dex_file.cc
@@ -37,6 +37,7 @@
#include "dex_file-inl.h"
#include "dex_file_verifier.h"
#include "globals.h"
+#include "handle_scope-inl.h"
#include "leb128.h"
#include "mirror/field.h"
#include "mirror/method.h"
@@ -44,8 +45,8 @@
#include "os.h"
#include "reflection.h"
#include "safe_map.h"
-#include "handle_scope-inl.h"
#include "thread.h"
+#include "type_lookup_table.h"
#include "utf-inl.h"
#include "utils.h"
#include "well_known_classes.h"
@@ -414,11 +415,19 @@
method_ids_(reinterpret_cast<const MethodId*>(base + header_->method_ids_off_)),
proto_ids_(reinterpret_cast<const ProtoId*>(base + header_->proto_ids_off_)),
class_defs_(reinterpret_cast<const ClassDef*>(base + header_->class_defs_off_)),
- find_class_def_misses_(0),
- class_def_index_(nullptr),
oat_dex_file_(oat_dex_file) {
CHECK(begin_ != nullptr) << GetLocation();
CHECK_GT(size_, 0U) << GetLocation();
+ const uint8_t* lookup_data = (oat_dex_file != nullptr)
+ ? oat_dex_file->GetLookupTableData()
+ : nullptr;
+ if (lookup_data != nullptr) {
+ if (lookup_data + TypeLookupTable::RawDataLength(*this) > oat_dex_file->GetOatFile()->End()) {
+ LOG(WARNING) << "found truncated lookup table in " << GetLocation();
+ } else {
+ lookup_table_.reset(TypeLookupTable::Open(lookup_data, *this));
+ }
+ }
}
DexFile::~DexFile() {
@@ -426,8 +435,6 @@
// that's only called after DetachCurrentThread, which means there's no JNIEnv. We could
// re-attach, but cleaning up these global references is not obviously useful. It's not as if
// the global reference table is otherwise empty!
- // Remove the index if one were created.
- delete class_def_index_.LoadRelaxed();
}
bool DexFile::Init(std::string* error_msg) {
@@ -477,51 +484,26 @@
const DexFile::ClassDef* DexFile::FindClassDef(const char* descriptor, size_t hash) const {
DCHECK_EQ(ComputeModifiedUtf8Hash(descriptor), hash);
- // If we have an index lookup the descriptor via that as its constant time to search.
- Index* index = class_def_index_.LoadSequentiallyConsistent();
- if (index != nullptr) {
- auto it = index->FindWithHash(descriptor, hash);
- return (it == index->end()) ? nullptr : it->second;
+ if (LIKELY(lookup_table_ != nullptr)) {
+ const uint32_t class_def_idx = lookup_table_->Lookup(descriptor, hash);
+ return (class_def_idx != DexFile::kDexNoIndex) ? &GetClassDef(class_def_idx) : nullptr;
}
+
// Fast path for rate no class defs case.
- uint32_t num_class_defs = NumClassDefs();
+ const uint32_t num_class_defs = NumClassDefs();
if (num_class_defs == 0) {
return nullptr;
}
- // Search for class def with 2 binary searches and then a linear search.
- const StringId* string_id = FindStringId(descriptor);
- if (string_id != nullptr) {
- const TypeId* type_id = FindTypeId(GetIndexForStringId(*string_id));
- if (type_id != nullptr) {
- uint16_t type_idx = GetIndexForTypeId(*type_id);
- for (size_t i = 0; i < num_class_defs; ++i) {
- const ClassDef& class_def = GetClassDef(i);
- if (class_def.class_idx_ == type_idx) {
- return &class_def;
- }
+ const TypeId* type_id = FindTypeId(descriptor);
+ if (type_id != nullptr) {
+ uint16_t type_idx = GetIndexForTypeId(*type_id);
+ for (size_t i = 0; i < num_class_defs; ++i) {
+ const ClassDef& class_def = GetClassDef(i);
+ if (class_def.class_idx_ == type_idx) {
+ return &class_def;
}
}
}
- // A miss. If we've had kMaxFailedDexClassDefLookups misses then build an index to speed things
- // up. This isn't done eagerly at construction as construction is not performed in multi-threaded
- // sections of tools like dex2oat. If we're lazy we hopefully increase the chance of balancing
- // out which thread builds the index.
- const uint32_t kMaxFailedDexClassDefLookups = 100;
- uint32_t old_misses = find_class_def_misses_.FetchAndAddSequentiallyConsistent(1);
- if (old_misses == kMaxFailedDexClassDefLookups) {
- // Are we the ones moving the miss count past the max? Sanity check the index doesn't exist.
- CHECK(class_def_index_.LoadSequentiallyConsistent() == nullptr);
- // Build the index.
- index = new Index();
- for (uint32_t i = 0; i < num_class_defs; ++i) {
- const ClassDef& class_def = GetClassDef(i);
- const char* class_descriptor = GetClassDescriptor(class_def);
- index->Insert(std::make_pair(class_descriptor, &class_def));
- }
- // Sanity check the index still doesn't exist, only 1 thread should build it.
- CHECK(class_def_index_.LoadSequentiallyConsistent() == nullptr);
- class_def_index_.StoreSequentiallyConsistent(index);
- }
return nullptr;
}
@@ -625,6 +607,26 @@
return nullptr;
}
+const DexFile::TypeId* DexFile::FindTypeId(const char* string) const {
+ int32_t lo = 0;
+ int32_t hi = NumTypeIds() - 1;
+ while (hi >= lo) {
+ int32_t mid = (hi + lo) / 2;
+ const TypeId& type_id = GetTypeId(mid);
+ const DexFile::StringId& str_id = GetStringId(type_id.descriptor_idx_);
+ const char* str = GetStringData(str_id);
+ int compare = CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(string, str);
+ if (compare > 0) {
+ lo = mid + 1;
+ } else if (compare < 0) {
+ hi = mid - 1;
+ } else {
+ return &type_id;
+ }
+ }
+ return nullptr;
+}
+
const DexFile::StringId* DexFile::FindStringId(const uint16_t* string, size_t length) const {
int32_t lo = 0;
int32_t hi = NumStringIds() - 1;
@@ -697,6 +699,10 @@
return nullptr;
}
+void DexFile::CreateTypeLookupTable() const {
+ lookup_table_.reset(TypeLookupTable::Create(*this));
+}
+
// Given a signature place the type ids into the given vector
bool DexFile::CreateTypeList(const StringPiece& signature, uint16_t* return_type_idx,
std::vector<uint16_t>* param_type_idxs) const {
diff --git a/runtime/dex_file.h b/runtime/dex_file.h
index 47e5c12..e7877b2 100644
--- a/runtime/dex_file.h
+++ b/runtime/dex_file.h
@@ -51,6 +51,7 @@
class Signature;
template<class T> class Handle;
class StringPiece;
+class TypeLookupTable;
class ZipArchive;
// TODO: move all of the macro functionality into the DexCache class.
@@ -532,6 +533,8 @@
// Looks up a string id for a given modified utf8 string.
const StringId* FindStringId(const char* string) const;
+ const TypeId* FindTypeId(const char* string) const;
+
// Looks up a string id for a given utf16 string.
const StringId* FindStringId(const uint16_t* string, size_t length) const;
@@ -1139,6 +1142,12 @@
return oat_dex_file_;
}
+ TypeLookupTable* GetTypeLookupTable() const {
+ return lookup_table_.get();
+ }
+
+ void CreateTypeLookupTable() const;
+
private:
// Opens a .dex file
static std::unique_ptr<const DexFile> OpenFile(int fd, const char* location,
@@ -1237,44 +1246,11 @@
// Points to the base of the class definition list.
const ClassDef* const class_defs_;
- // Number of misses finding a class def from a descriptor.
- mutable Atomic<uint32_t> find_class_def_misses_;
-
- struct UTF16EmptyFn {
- void MakeEmpty(std::pair<const char*, const ClassDef*>& pair) const {
- pair.first = nullptr;
- pair.second = nullptr;
- }
- bool IsEmpty(const std::pair<const char*, const ClassDef*>& pair) const {
- if (pair.first == nullptr) {
- DCHECK(pair.second == nullptr);
- return true;
- }
- return false;
- }
- };
- struct UTF16HashCmp {
- // Hash function.
- size_t operator()(const char* key) const {
- return ComputeModifiedUtf8Hash(key);
- }
- // std::equal function.
- bool operator()(const char* a, const char* b) const {
- return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(a, b) == 0;
- }
- };
- using Index = HashMap<const char*,
- const ClassDef*,
- UTF16EmptyFn,
- UTF16HashCmp,
- UTF16HashCmp,
- std::allocator<std::pair<const char*, const ClassDef*>>>;
- mutable Atomic<Index*> class_def_index_;
-
// If this dex file was loaded from an oat file, oat_dex_file_ contains a
// pointer to the OatDexFile it was loaded from. Otherwise oat_dex_file_ is
// null.
const OatDexFile* oat_dex_file_;
+ mutable std::unique_ptr<TypeLookupTable> lookup_table_;
friend class DexFileVerifierTest;
};
diff --git a/runtime/oat.h b/runtime/oat.h
index 276e7f3..5b780c3 100644
--- a/runtime/oat.h
+++ b/runtime/oat.h
@@ -31,7 +31,7 @@
class PACKED(4) OatHeader {
public:
static constexpr uint8_t kOatMagic[] = { 'o', 'a', 't', '\n' };
- static constexpr uint8_t kOatVersion[] = { '0', '7', '2', '\0' };
+ static constexpr uint8_t kOatVersion[] = { '0', '7', '3', '\0' };
static constexpr const char* kImageLocationKey = "image-location";
static constexpr const char* kDex2OatCmdLineKey = "dex2oat-cmdline";
diff --git a/runtime/oat_file.cc b/runtime/oat_file.cc
index a162a4e..680f4ac 100644
--- a/runtime/oat_file.cc
+++ b/runtime/oat_file.cc
@@ -547,6 +547,25 @@
return false;
}
const DexFile::Header* header = reinterpret_cast<const DexFile::Header*>(dex_file_pointer);
+
+ if (UNLIKELY(oat > End())) {
+ *error_msg = StringPrintf("In oat file '%s' found OatDexFile #%zd for '%s' with truncated "
+ "lookup table offset", GetLocation().c_str(), i,
+ dex_file_location.c_str());
+ return false;
+ }
+ uint32_t lookup_table_offset = *reinterpret_cast<const uint32_t*>(oat);
+ oat += sizeof(lookup_table_offset);
+ if (Begin() + lookup_table_offset > End()) {
+ *error_msg = StringPrintf("In oat file '%s' found OatDexFile #%zd for '%s' with truncated "
+ "lookup table", GetLocation().c_str(), i,
+ dex_file_location.c_str());
+ return false;
+ }
+ const uint8_t* lookup_table_data = lookup_table_offset != 0u
+ ? Begin() + lookup_table_offset
+ : nullptr;
+
const uint32_t* methods_offsets_pointer = reinterpret_cast<const uint32_t*>(oat);
oat += (sizeof(*methods_offsets_pointer) * header->class_defs_size_);
@@ -586,6 +605,7 @@
canonical_location,
dex_file_checksum,
dex_file_pointer,
+ lookup_table_data,
methods_offsets_pointer,
current_dex_cache_arrays);
oat_dex_files_storage_.push_back(oat_dex_file);
@@ -709,6 +729,7 @@
const std::string& canonical_dex_file_location,
uint32_t dex_file_location_checksum,
const uint8_t* dex_file_pointer,
+ const uint8_t* lookup_table_data,
const uint32_t* oat_class_offsets_pointer,
uint8_t* dex_cache_arrays)
: oat_file_(oat_file),
@@ -716,6 +737,7 @@
canonical_dex_file_location_(canonical_dex_file_location),
dex_file_location_checksum_(dex_file_location_checksum),
dex_file_pointer_(dex_file_pointer),
+ lookup_table_data_(lookup_table_data),
oat_class_offsets_pointer_(oat_class_offsets_pointer),
dex_cache_arrays_(dex_cache_arrays) {}
diff --git a/runtime/oat_file.h b/runtime/oat_file.h
index 6acdf86..0a77654 100644
--- a/runtime/oat_file.h
+++ b/runtime/oat_file.h
@@ -400,6 +400,10 @@
return dex_cache_arrays_;
}
+ const uint8_t* GetLookupTableData() const {
+ return lookup_table_data_;
+ }
+
~OatDexFile();
private:
@@ -408,6 +412,7 @@
const std::string& canonical_dex_file_location,
uint32_t dex_file_checksum,
const uint8_t* dex_file_pointer,
+ const uint8_t* lookup_table_data,
const uint32_t* oat_class_offsets_pointer,
uint8_t* dex_cache_arrays);
@@ -416,6 +421,7 @@
const std::string canonical_dex_file_location_;
const uint32_t dex_file_location_checksum_;
const uint8_t* const dex_file_pointer_;
+ const uint8_t* lookup_table_data_;
const uint32_t* const oat_class_offsets_pointer_;
uint8_t* const dex_cache_arrays_;
diff --git a/runtime/type_lookup_table.cc b/runtime/type_lookup_table.cc
new file mode 100644
index 0000000..0d40bb7
--- /dev/null
+++ b/runtime/type_lookup_table.cc
@@ -0,0 +1,131 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "type_lookup_table.h"
+
+#include "dex_file-inl.h"
+#include "utf-inl.h"
+#include "utils.h"
+
+#include <memory>
+#include <cstring>
+
+namespace art {
+
+static uint16_t MakeData(uint16_t class_def_idx, uint32_t hash, uint32_t mask) {
+ uint16_t hash_mask = static_cast<uint16_t>(~mask);
+ return (static_cast<uint16_t>(hash) & hash_mask) | class_def_idx;
+}
+
+TypeLookupTable::~TypeLookupTable() {
+ if (!owns_entries_) {
+ // We don't actually own the entries, don't let the unique_ptr release them.
+ entries_.release();
+ }
+}
+
+uint32_t TypeLookupTable::RawDataLength() const {
+ return RawDataLength(dex_file_);
+}
+
+uint32_t TypeLookupTable::RawDataLength(const DexFile& dex_file) {
+ return RoundUpToPowerOfTwo(dex_file.NumClassDefs()) * sizeof(Entry);
+}
+
+TypeLookupTable* TypeLookupTable::Create(const DexFile& dex_file) {
+ const uint32_t num_class_defs = dex_file.NumClassDefs();
+ return (num_class_defs == 0 || num_class_defs > std::numeric_limits<uint16_t>::max())
+ ? nullptr
+ : new TypeLookupTable(dex_file);
+}
+
+TypeLookupTable* TypeLookupTable::Open(const uint8_t* raw_data, const DexFile& dex_file) {
+ return new TypeLookupTable(raw_data, dex_file);
+}
+
+TypeLookupTable::TypeLookupTable(const DexFile& dex_file)
+ : dex_file_(dex_file),
+ mask_(RoundUpToPowerOfTwo(dex_file.NumClassDefs()) - 1),
+ entries_(new Entry[mask_ + 1]),
+ owns_entries_(true) {
+ std::vector<uint16_t> conflict_class_defs;
+ // The first stage. Put elements on their initial positions. If an initial position is already
+ // occupied then delay the insertion of the element to the second stage to reduce probing
+ // distance.
+ for (size_t i = 0; i < dex_file.NumClassDefs(); ++i) {
+ const DexFile::ClassDef& class_def = dex_file.GetClassDef(i);
+ const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
+ const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
+ const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
+ Entry entry;
+ entry.str_offset = str_id.string_data_off_;
+ entry.data = MakeData(i, hash, GetSizeMask());
+ if (!SetOnInitialPos(entry, hash)) {
+ conflict_class_defs.push_back(i);
+ }
+ }
+ // The second stage. The initial position of these elements had a collision. Put these elements
+ // into the nearest free cells and link them together by updating next_pos_delta.
+ for (uint16_t class_def_idx : conflict_class_defs) {
+ const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
+ const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
+ const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
+ const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
+ Entry entry;
+ entry.str_offset = str_id.string_data_off_;
+ entry.data = MakeData(class_def_idx, hash, GetSizeMask());
+ Insert(entry, hash);
+ }
+}
+
+TypeLookupTable::TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file)
+ : dex_file_(dex_file),
+ mask_(RoundUpToPowerOfTwo(dex_file.NumClassDefs()) - 1),
+ entries_(reinterpret_cast<Entry*>(const_cast<uint8_t*>(raw_data))),
+ owns_entries_(false) {}
+
+bool TypeLookupTable::SetOnInitialPos(const Entry& entry, uint32_t hash) {
+ const uint32_t pos = hash & GetSizeMask();
+ if (!entries_[pos].IsEmpty()) {
+ return false;
+ }
+ entries_[pos] = entry;
+ entries_[pos].next_pos_delta = 0;
+ return true;
+}
+
+void TypeLookupTable::Insert(const Entry& entry, uint32_t hash) {
+ uint32_t pos = FindLastEntryInBucket(hash & GetSizeMask());
+ uint32_t next_pos = (pos + 1) & GetSizeMask();
+ while (!entries_[next_pos].IsEmpty()) {
+ next_pos = (next_pos + 1) & GetSizeMask();
+ }
+ const uint32_t delta = (next_pos >= pos) ? (next_pos - pos) : (next_pos + Size() - pos);
+ entries_[pos].next_pos_delta = delta;
+ entries_[next_pos] = entry;
+ entries_[next_pos].next_pos_delta = 0;
+}
+
+uint32_t TypeLookupTable::FindLastEntryInBucket(uint32_t pos) const {
+ const Entry* entry = &entries_[pos];
+ while (!entry->IsLast()) {
+ pos = (pos + entry->next_pos_delta) & GetSizeMask();
+ entry = &entries_[pos];
+ }
+ return pos;
+}
+
+} // namespace art
diff --git a/runtime/type_lookup_table.h b/runtime/type_lookup_table.h
new file mode 100644
index 0000000..3c2295c
--- /dev/null
+++ b/runtime/type_lookup_table.h
@@ -0,0 +1,162 @@
+/*
+ * Copyright (C) 2015 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_RUNTIME_TYPE_LOOKUP_TABLE_H_
+#define ART_RUNTIME_TYPE_LOOKUP_TABLE_H_
+
+#include "dex_file.h"
+#include "leb128.h"
+#include "utf.h"
+
+namespace art {
+
+/**
+ * TypeLookupTable used to find class_def_idx by class descriptor quickly.
+ * Implementation of TypeLookupTable is based on hash table.
+ * This class instantiated at compile time by calling Create() method and written into OAT file.
+ * At runtime, the raw data is read from memory-mapped file by calling Open() method. The table
+ * memory remains clean.
+ */
+class TypeLookupTable {
+ public:
+ ~TypeLookupTable();
+
+ // Return the number of buckets in the lookup table.
+ uint32_t Size() const {
+ return mask_ + 1;
+ }
+
+ // Method search class_def_idx by class descriptor and it's hash.
+ // If no data found then the method returns DexFile::kDexNoIndex
+ ALWAYS_INLINE uint32_t Lookup(const char* str, uint32_t hash) const {
+ uint32_t pos = hash & GetSizeMask();
+ // Thanks to special insertion algorithm, the element at position pos can be empty or start of
+ // bucket.
+ const Entry* entry = &entries_[pos];
+ while (!entry->IsEmpty()) {
+ if (CmpHashBits(entry->data, hash) && IsStringsEquals(str, entry->str_offset)) {
+ return GetClassDefIdx(entry->data);
+ }
+ if (entry->IsLast()) {
+ return DexFile::kDexNoIndex;
+ }
+ pos = (pos + entry->next_pos_delta) & GetSizeMask();
+ entry = &entries_[pos];
+ }
+ return DexFile::kDexNoIndex;
+ }
+
+ // Method creates lookup table for dex file
+ static TypeLookupTable* Create(const DexFile& dex_file);
+
+ // Method opens lookup table from binary data. Lookup table does not owns binary data.
+ static TypeLookupTable* Open(const uint8_t* raw_data, const DexFile& dex_file);
+
+ // Method returns pointer to binary data of lookup table. Used by the oat writer.
+ const uint8_t* RawData() const {
+ return reinterpret_cast<const uint8_t*>(entries_.get());
+ }
+
+ // Method returns length of binary data. Used by the oat writer.
+ uint32_t RawDataLength() const;
+
+ // Method returns length of binary data for the specified dex file.
+ static uint32_t RawDataLength(const DexFile& dex_file);
+
+ private:
+ /**
+ * To find element we need to compare strings.
+ * It is faster to compare first hashes and then strings itself.
+ * But we have no full hash of element of table. But we can use 2 ideas.
+ * 1. All minor bits of hash inside one bucket are equals.
+ * 2. If dex file contains N classes and size of hash table is 2^n (where N <= 2^n)
+ * then 16-n bits are free. So we can encode part of element's hash into these bits.
+ * So hash of element can be divided on three parts:
+ * XXXX XXXX XXXX YYYY YZZZ ZZZZ ZZZZZ
+ * Z - a part of hash encoded in bucket (these bits of has are same for all elements in bucket) -
+ * n bits
+ * Y - a part of hash that we can write into free 16-n bits (because only n bits used to store
+ * class_def_idx)
+ * X - a part of has that we can't use without increasing increase
+ * So the data element of Entry used to store class_def_idx and part of hash of the entry.
+ */
+ struct Entry {
+ uint32_t str_offset;
+ uint16_t data;
+ uint16_t next_pos_delta;
+
+ Entry() : str_offset(0), data(0), next_pos_delta(0) {}
+
+ bool IsEmpty() const {
+ return str_offset == 0;
+ }
+
+ bool IsLast() const {
+ return next_pos_delta == 0;
+ }
+ };
+
+ // Construct from a dex file.
+ explicit TypeLookupTable(const DexFile& dex_file);
+
+ // Construct from a dex file with existing data.
+ TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file);
+
+ bool IsStringsEquals(const char* str, uint32_t str_offset) const {
+ const uint8_t* ptr = dex_file_.Begin() + str_offset;
+ // Skip string length.
+ DecodeUnsignedLeb128(&ptr);
+ return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(
+ str, reinterpret_cast<const char*>(ptr)) == 0;
+ }
+
+ // Method extracts hash bits from element's data and compare them with
+ // the corresponding bits of the specified hash
+ bool CmpHashBits(uint32_t data, uint32_t hash) const {
+ uint32_t mask = static_cast<uint16_t>(~GetSizeMask());
+ return (hash & mask) == (data & mask);
+ }
+
+ uint32_t GetClassDefIdx(uint32_t data) const {
+ return data & mask_;
+ }
+
+ uint32_t GetSizeMask() const {
+ return mask_;
+ }
+
+ // Attempt to set an entry on it's hash' slot. If there is alrady something there, return false.
+ // Otherwise return true.
+ bool SetOnInitialPos(const Entry& entry, uint32_t hash);
+
+ // Insert an entry, probes until there is an empty slot.
+ void Insert(const Entry& entry, uint32_t hash);
+
+ // Find the last entry in a chain.
+ uint32_t FindLastEntryInBucket(uint32_t cur_pos) const;
+
+ const DexFile& dex_file_;
+ const uint32_t mask_;
+ std::unique_ptr<Entry[]> entries_;
+ // owns_entries_ specifies if the lookup table owns the entries_ array.
+ const bool owns_entries_;
+
+ DISALLOW_IMPLICIT_CONSTRUCTORS(TypeLookupTable);
+};
+
+} // namespace art
+
+#endif // ART_RUNTIME_TYPE_LOOKUP_TABLE_H_
diff --git a/runtime/type_lookup_table_test.cc b/runtime/type_lookup_table_test.cc
new file mode 100644
index 0000000..7f500cc
--- /dev/null
+++ b/runtime/type_lookup_table_test.cc
@@ -0,0 +1,86 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+#include <memory>
+
+#include "common_runtime_test.h"
+#include "dex_file-inl.h"
+#include "scoped_thread_state_change.h"
+#include "type_lookup_table.h"
+#include "utf-inl.h"
+
+namespace art {
+
+class TypeLookupTableTest : public CommonRuntimeTest {
+ public:
+ size_t kDexNoIndex = DexFile::kDexNoIndex; // Make copy to prevent linking errors.
+};
+
+TEST_F(TypeLookupTableTest, CreateLookupTable) {
+ ScopedObjectAccess soa(Thread::Current());
+ std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup"));
+ std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file));
+ ASSERT_NE(nullptr, table.get());
+ ASSERT_NE(nullptr, table->RawData());
+ ASSERT_EQ(32U, table->RawDataLength());
+}
+
+TEST_F(TypeLookupTableTest, FindNonExistingClassWithoutCollisions) {
+ ScopedObjectAccess soa(Thread::Current());
+ std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup"));
+ std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file));
+ ASSERT_NE(nullptr, table.get());
+ const char* descriptor = "LBA;";
+ size_t hash = ComputeModifiedUtf8Hash(descriptor);
+ uint32_t class_def_idx = table->Lookup(descriptor, hash);
+ ASSERT_EQ(kDexNoIndex, class_def_idx);
+}
+
+TEST_F(TypeLookupTableTest, FindNonExistingClassWithCollisions) {
+ ScopedObjectAccess soa(Thread::Current());
+ std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup"));
+ std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file));
+ ASSERT_NE(nullptr, table.get());
+ const char* descriptor = "LDA;";
+ size_t hash = ComputeModifiedUtf8Hash(descriptor);
+ uint32_t class_def_idx = table->Lookup(descriptor, hash);
+ ASSERT_EQ(kDexNoIndex, class_def_idx);
+}
+
+TEST_F(TypeLookupTableTest, FindClassNoCollisions) {
+ ScopedObjectAccess soa(Thread::Current());
+ std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup"));
+ std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file));
+ ASSERT_NE(nullptr, table.get());
+ const char* descriptor = "LC;";
+ size_t hash = ComputeModifiedUtf8Hash(descriptor);
+ uint32_t class_def_idx = table->Lookup(descriptor, hash);
+ ASSERT_EQ(2U, class_def_idx);
+}
+
+TEST_F(TypeLookupTableTest, FindClassWithCollisions) {
+ ScopedObjectAccess soa(Thread::Current());
+ std::unique_ptr<const DexFile> dex_file(OpenTestDexFile("Lookup"));
+ std::unique_ptr<TypeLookupTable> table(TypeLookupTable::Create(*dex_file));
+ ASSERT_NE(nullptr, table.get());
+ const char* descriptor = "LAB;";
+ size_t hash = ComputeModifiedUtf8Hash(descriptor);
+ uint32_t class_def_idx = table->Lookup(descriptor, hash);
+ ASSERT_EQ(1U, class_def_idx);
+}
+
+} // namespace art