1 /* 2 * Copyright (C) 2015 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef ART_RUNTIME_TYPE_LOOKUP_TABLE_H_ 18 #define ART_RUNTIME_TYPE_LOOKUP_TABLE_H_ 19 20 #include "dex_file.h" 21 #include "leb128.h" 22 #include "utf.h" 23 24 namespace art { 25 26 /** 27 * TypeLookupTable used to find class_def_idx by class descriptor quickly. 28 * Implementation of TypeLookupTable is based on hash table. 29 * This class instantiated at compile time by calling Create() method and written into OAT file. 30 * At runtime, the raw data is read from memory-mapped file by calling Open() method. The table 31 * memory remains clean. 32 */ 33 class TypeLookupTable { 34 public: 35 ~TypeLookupTable(); 36 37 // Return the number of buckets in the lookup table. 38 uint32_t Size() const { 39 return mask_ + 1; 40 } 41 42 // Method search class_def_idx by class descriptor and it's hash. 43 // If no data found then the method returns DexFile::kDexNoIndex 44 ALWAYS_INLINE uint32_t Lookup(const char* str, uint32_t hash) const { 45 uint32_t pos = hash & GetSizeMask(); 46 // Thanks to special insertion algorithm, the element at position pos can be empty or start of 47 // bucket. 48 const Entry* entry = &entries_[pos]; 49 while (!entry->IsEmpty()) { 50 if (CmpHashBits(entry->data, hash) && IsStringsEquals(str, entry->str_offset)) { 51 return GetClassDefIdx(entry->data); 52 } 53 if (entry->IsLast()) { 54 return DexFile::kDexNoIndex; 55 } 56 pos = (pos + entry->next_pos_delta) & GetSizeMask(); 57 entry = &entries_[pos]; 58 } 59 return DexFile::kDexNoIndex; 60 } 61 62 // Method creates lookup table for dex file 63 static TypeLookupTable* Create(const DexFile& dex_file, uint8_t* storage = nullptr); 64 65 // Method opens lookup table from binary data. Lookup table does not owns binary data. 66 static TypeLookupTable* Open(const uint8_t* raw_data, const DexFile& dex_file); 67 68 // Method returns pointer to binary data of lookup table. Used by the oat writer. 69 const uint8_t* RawData() const { 70 return reinterpret_cast<const uint8_t*>(entries_.get()); 71 } 72 73 // Method returns length of binary data. Used by the oat writer. 74 uint32_t RawDataLength() const; 75 76 // Method returns length of binary data for the specified dex file. 77 static uint32_t RawDataLength(const DexFile& dex_file); 78 79 // Method returns length of binary data for the specified number of class definitions. 80 static uint32_t RawDataLength(uint32_t num_class_defs); 81 82 private: 83 /** 84 * To find element we need to compare strings. 85 * It is faster to compare first hashes and then strings itself. 86 * But we have no full hash of element of table. But we can use 2 ideas. 87 * 1. All minor bits of hash inside one bucket are equals. 88 * 2. If dex file contains N classes and size of hash table is 2^n (where N <= 2^n) 89 * then 16-n bits are free. So we can encode part of element's hash into these bits. 90 * So hash of element can be divided on three parts: 91 * XXXX XXXX XXXX YYYY YZZZ ZZZZ ZZZZZ 92 * Z - a part of hash encoded in bucket (these bits of has are same for all elements in bucket) - 93 * n bits 94 * Y - a part of hash that we can write into free 16-n bits (because only n bits used to store 95 * class_def_idx) 96 * X - a part of has that we can't use without increasing increase 97 * So the data element of Entry used to store class_def_idx and part of hash of the entry. 98 */ 99 struct Entry { 100 uint32_t str_offset; 101 uint16_t data; 102 uint16_t next_pos_delta; 103 104 Entry() : str_offset(0), data(0), next_pos_delta(0) {} 105 106 bool IsEmpty() const { 107 return str_offset == 0; 108 } 109 110 bool IsLast() const { 111 return next_pos_delta == 0; 112 } 113 }; 114 115 static uint32_t CalculateMask(uint32_t num_class_defs); 116 static bool SupportedSize(uint32_t num_class_defs); 117 118 // Construct from a dex file. 119 explicit TypeLookupTable(const DexFile& dex_file, uint8_t* storage); 120 121 // Construct from a dex file with existing data. 122 TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file); 123 124 bool IsStringsEquals(const char* str, uint32_t str_offset) const { 125 const uint8_t* ptr = dex_file_.Begin() + str_offset; 126 // Skip string length. 127 DecodeUnsignedLeb128(&ptr); 128 return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues( 129 str, reinterpret_cast<const char*>(ptr)) == 0; 130 } 131 132 // Method extracts hash bits from element's data and compare them with 133 // the corresponding bits of the specified hash 134 bool CmpHashBits(uint32_t data, uint32_t hash) const { 135 uint32_t mask = static_cast<uint16_t>(~GetSizeMask()); 136 return (hash & mask) == (data & mask); 137 } 138 139 uint32_t GetClassDefIdx(uint32_t data) const { 140 return data & mask_; 141 } 142 143 uint32_t GetSizeMask() const { 144 return mask_; 145 } 146 147 // Attempt to set an entry on it's hash' slot. If there is alrady something there, return false. 148 // Otherwise return true. 149 bool SetOnInitialPos(const Entry& entry, uint32_t hash); 150 151 // Insert an entry, probes until there is an empty slot. 152 void Insert(const Entry& entry, uint32_t hash); 153 154 // Find the last entry in a chain. 155 uint32_t FindLastEntryInBucket(uint32_t cur_pos) const; 156 157 const DexFile& dex_file_; 158 const uint32_t mask_; 159 std::unique_ptr<Entry[]> entries_; 160 // owns_entries_ specifies if the lookup table owns the entries_ array. 161 const bool owns_entries_; 162 163 DISALLOW_IMPLICIT_CONSTRUCTORS(TypeLookupTable); 164 }; 165 166 } // namespace art 167 168 #endif // ART_RUNTIME_TYPE_LOOKUP_TABLE_H_ 169
