diff options
Diffstat (limited to 'libdexfile')
| -rw-r--r-- | libdexfile/Android.bp | 2 | ||||
| -rw-r--r-- | libdexfile/dex/type_lookup_table.cc | 145 | ||||
| -rw-r--r-- | libdexfile/dex/type_lookup_table.h | 175 | ||||
| -rw-r--r-- | libdexfile/dex/type_lookup_table_test.cc | 64 |
4 files changed, 386 insertions, 0 deletions
diff --git a/libdexfile/Android.bp b/libdexfile/Android.bp index 3fd61ee251..b2c041c81f 100644 --- a/libdexfile/Android.bp +++ b/libdexfile/Android.bp @@ -32,6 +32,7 @@ cc_defaults { "dex/modifiers.cc", "dex/primitive.cc", "dex/standard_dex_file.cc", + "dex/type_lookup_table.cc", "dex/utf.cc", ], @@ -123,6 +124,7 @@ art_cc_test { "dex/dex_instruction_test.cc", "dex/primitive_test.cc", "dex/string_reference_test.cc", + "dex/type_lookup_table_test.cc", "dex/utf_test.cc", ], shared_libs: [ diff --git a/libdexfile/dex/type_lookup_table.cc b/libdexfile/dex/type_lookup_table.cc new file mode 100644 index 0000000000..ca5ec2f798 --- /dev/null +++ b/libdexfile/dex/type_lookup_table.cc @@ -0,0 +1,145 @@ +/* + * 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 <cstring> +#include <memory> + +#include "base/bit_utils.h" +#include "dex/dex_file-inl.h" +#include "dex/utf-inl.h" + +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(uint32_t num_class_defs) { + return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) * sizeof(Entry) : 0u; +} + +uint32_t TypeLookupTable::CalculateMask(uint32_t num_class_defs) { + return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) - 1u : 0u; +} + +bool TypeLookupTable::SupportedSize(uint32_t num_class_defs) { + return num_class_defs != 0u && num_class_defs <= std::numeric_limits<uint16_t>::max(); +} + +std::unique_ptr<TypeLookupTable> TypeLookupTable::Create(const DexFile& dex_file, + uint8_t* storage) { + const uint32_t num_class_defs = dex_file.NumClassDefs(); + return std::unique_ptr<TypeLookupTable>(SupportedSize(num_class_defs) + ? new TypeLookupTable(dex_file, storage) + : nullptr); +} + +std::unique_ptr<TypeLookupTable> TypeLookupTable::Open(const uint8_t* dex_file_pointer, + const uint8_t* raw_data, + uint32_t num_class_defs) { + return std::unique_ptr<TypeLookupTable>( + new TypeLookupTable(dex_file_pointer, raw_data, num_class_defs)); +} + +TypeLookupTable::TypeLookupTable(const DexFile& dex_file, uint8_t* storage) + : dex_data_begin_(dex_file.DataBegin()), + raw_data_length_(RawDataLength(dex_file.NumClassDefs())), + mask_(CalculateMask(dex_file.NumClassDefs())), + entries_(storage != nullptr ? reinterpret_cast<Entry*>(storage) : new Entry[mask_ + 1]), + owns_entries_(storage == nullptr) { + static_assert(alignof(Entry) == 4u, "Expecting Entry to be 4-byte aligned."); + DCHECK_ALIGNED(storage, alignof(Entry)); + 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* dex_file_pointer, + const uint8_t* raw_data, + uint32_t num_class_defs) + : dex_data_begin_(dex_file_pointer), + raw_data_length_(RawDataLength(num_class_defs)), + mask_(CalculateMask(num_class_defs)), + 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/libdexfile/dex/type_lookup_table.h b/libdexfile/dex/type_lookup_table.h new file mode 100644 index 0000000000..0ba2b75dc6 --- /dev/null +++ b/libdexfile/dex/type_lookup_table.h @@ -0,0 +1,175 @@ +/* + * 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_LIBDEXFILE_DEX_TYPE_LOOKUP_TABLE_H_ +#define ART_LIBDEXFILE_DEX_TYPE_LOOKUP_TABLE_H_ + +#include "base/leb128.h" +#include "dex/dex_file_types.h" +#include "dex/utf.h" + +namespace art { + +class DexFile; + +/** + * 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 dex::kDexNoIndex. + 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 dex::kDexNoIndex; + } + pos = (pos + entry->next_pos_delta) & GetSizeMask(); + entry = &entries_[pos]; + } + return dex::kDexNoIndex; + } + + // Method creates lookup table for dex file + static std::unique_ptr<TypeLookupTable> Create(const DexFile& dex_file, + uint8_t* storage = nullptr); + + // Method opens lookup table from binary data. Lookups will traverse strings and other + // data contained in dex_file as well. Lookup table does not own raw_data or dex_file. + static std::unique_ptr<TypeLookupTable> Open(const uint8_t* dex_file_pointer, + const uint8_t* raw_data, + uint32_t num_class_defs); + + // 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 { return raw_data_length_; } + + // Method returns length of binary data for the specified number of class definitions. + static uint32_t RawDataLength(uint32_t num_class_defs); + + 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; + } + }; + + static uint32_t CalculateMask(uint32_t num_class_defs); + static bool SupportedSize(uint32_t num_class_defs); + + // Construct from a dex file. + explicit TypeLookupTable(const DexFile& dex_file, uint8_t* storage); + + // Construct from a dex file with existing data. + TypeLookupTable(const uint8_t* dex_file_pointer, + const uint8_t* raw_data, + uint32_t num_class_defs); + + bool IsStringsEquals(const char* str, uint32_t str_offset) const { + const uint8_t* ptr = dex_data_begin_ + str_offset; + CHECK(dex_data_begin_ != nullptr); + // 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 its hash's slot. If there is already 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 uint8_t* dex_data_begin_; + const uint32_t raw_data_length_; + 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_LIBDEXFILE_DEX_TYPE_LOOKUP_TABLE_H_ diff --git a/libdexfile/dex/type_lookup_table_test.cc b/libdexfile/dex/type_lookup_table_test.cc new file mode 100644 index 0000000000..b6ab6da78c --- /dev/null +++ b/libdexfile/dex/type_lookup_table_test.cc @@ -0,0 +1,64 @@ +/* + * 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 "type_lookup_table.h" + +#include <memory> + +#include "common_runtime_test.h" +#include "dex/dex_file-inl.h" +#include "dex/utf-inl.h" +#include "scoped_thread_state_change-inl.h" + +namespace art { + +using DescriptorClassDefIdxPair = std::pair<const char*, uint32_t>; +class TypeLookupTableTest : public CommonRuntimeTestWithParam<DescriptorClassDefIdxPair> {}; + +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_P(TypeLookupTableTest, Find) { + 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()); + auto pair = GetParam(); + const char* descriptor = pair.first; + size_t hash = ComputeModifiedUtf8Hash(descriptor); + uint32_t class_def_idx = table->Lookup(descriptor, hash); + ASSERT_EQ(pair.second, class_def_idx); +} + +INSTANTIATE_TEST_CASE_P(FindNonExistingClassWithoutCollisions, + TypeLookupTableTest, + testing::Values(DescriptorClassDefIdxPair("LAB;", 1U))); +INSTANTIATE_TEST_CASE_P(FindNonExistingClassWithCollisions, + TypeLookupTableTest, + testing::Values(DescriptorClassDefIdxPair("LDA;", dex::kDexNoIndex))); +INSTANTIATE_TEST_CASE_P(FindClassNoCollisions, + TypeLookupTableTest, + testing::Values(DescriptorClassDefIdxPair("LC;", 2U))); +INSTANTIATE_TEST_CASE_P(FindClassWithCollisions, + TypeLookupTableTest, + testing::Values(DescriptorClassDefIdxPair("LAB;", 1U))); +} // namespace art |