/* * 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 "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_RUNTIME_TYPE_LOOKUP_TABLE_H_