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_LIBDEXFILE_DEX_TYPE_LOOKUP_TABLE_H_ 18 #define ART_LIBDEXFILE_DEX_TYPE_LOOKUP_TABLE_H_ 19 20 #include <android-base/logging.h> 21 22 #include "dex/dex_file_types.h" 23 24 namespace art { 25 26 class DexFile; 27 28 /** 29 * TypeLookupTable used to find class_def_idx by class descriptor quickly. 30 * Implementation of TypeLookupTable is based on hash table. 31 * This class instantiated at compile time by calling Create() method and written into OAT file. 32 * At runtime, the raw data is read from memory-mapped file by calling Open() method. The table 33 * memory remains clean. 34 */ 35 class TypeLookupTable { 36 public: 37 // Method creates lookup table for dex file. 38 static TypeLookupTable Create(const DexFile& dex_file); 39 40 // Method opens lookup table from binary data. Lookups will traverse strings and other 41 // data contained in dex_file as well. Lookup table does not own raw_data or dex_file. 42 static TypeLookupTable Open(const uint8_t* dex_data_pointer, 43 const uint8_t* raw_data, 44 uint32_t num_class_defs); 45 46 // Create an invalid lookup table. TypeLookupTable()47 TypeLookupTable() 48 : dex_data_begin_(nullptr), 49 mask_bits_(0u), 50 entries_(nullptr), 51 owned_entries_(nullptr) {} 52 53 TypeLookupTable(TypeLookupTable&& src) noexcept = default; 54 TypeLookupTable& operator=(TypeLookupTable&& src) noexcept = default; 55 ~TypeLookupTable()56 ~TypeLookupTable() { 57 // Implicit deallocation by std::unique_ptr<> destructor. 58 } 59 60 // Returns whether the TypeLookupTable is valid. Valid()61 bool Valid() const { 62 return entries_ != nullptr; 63 } 64 65 // Return the number of buckets in the lookup table. Size()66 uint32_t Size() const { 67 DCHECK(Valid()); 68 return 1u << mask_bits_; 69 } 70 71 // Method search class_def_idx by class descriptor and it's hash. 72 // If no data found then the method returns dex::kDexNoIndex. 73 uint32_t Lookup(const char* str, uint32_t hash) const; 74 75 // Method returns pointer to binary data of lookup table. Used by the oat writer. RawData()76 const uint8_t* RawData() const { 77 DCHECK(Valid()); 78 return reinterpret_cast<const uint8_t*>(entries_); 79 } 80 81 // Method returns length of binary data. Used by the oat writer. RawDataLength()82 uint32_t RawDataLength() const { 83 DCHECK(Valid()); 84 return Size() * sizeof(Entry); 85 } 86 87 // Method returns length of binary data for the specified number of class definitions. 88 static uint32_t RawDataLength(uint32_t num_class_defs); 89 90 void Dump(std::ostream& os) const; 91 92 private: 93 /** 94 * To find element we need to compare strings. 95 * It is faster to compare first hashes and then strings itself. 96 * But we have no full hash of element of table. But we can use 2 ideas. 97 * 1. All minor bits of hash inside one bucket are equal. 98 * (TODO: We're not actually using this, are we?) 99 * 2. If the dex file contains N classes and the size of the hash table is 2^n (where N <= 2^n) 100 * then we need n bits for the class def index and n bits for the next position delta. 101 * So we can encode part of element's hash into the remaining 32-2*n (n <= 16) bits which 102 * would be otherwise wasted as a padding. 103 * So hash of element can be divided on three parts: 104 * XXXX XXXX XXXY YYYY YYYY YZZZ ZZZZ ZZZZ (example with n=11) 105 * Z - a part of hash encoded implicitly in the bucket index 106 * (these bits are same for all elements in bucket) 107 * Y - a part of hash that we can write into free 32-2*n bits 108 * X - a part of hash that we can't use without increasing the size of the entry 109 * So the `data` element of Entry is used to store the next position delta, class_def_index 110 * and a part of hash of the entry. 111 */ 112 class Entry { 113 public: Entry()114 Entry() : str_offset_(0u), data_(0u) {} Entry(uint32_t str_offset,uint32_t hash,uint32_t class_def_index,uint32_t mask_bits)115 Entry(uint32_t str_offset, uint32_t hash, uint32_t class_def_index, uint32_t mask_bits) 116 : str_offset_(str_offset), 117 data_(((hash & ~GetMask(mask_bits)) | class_def_index) << mask_bits) { 118 DCHECK_EQ(class_def_index & ~GetMask(mask_bits), 0u); 119 } 120 SetNextPosDelta(uint32_t next_pos_delta,uint32_t mask_bits)121 void SetNextPosDelta(uint32_t next_pos_delta, uint32_t mask_bits) { 122 DCHECK_EQ(GetNextPosDelta(mask_bits), 0u); 123 DCHECK_EQ(next_pos_delta & ~GetMask(mask_bits), 0u); 124 DCHECK_NE(next_pos_delta, 0u); 125 data_ |= next_pos_delta; 126 } 127 IsEmpty()128 bool IsEmpty() const { 129 return str_offset_ == 0u; 130 } 131 IsLast(uint32_t mask_bits)132 bool IsLast(uint32_t mask_bits) const { 133 return GetNextPosDelta(mask_bits) == 0u; 134 } 135 GetStringOffset()136 uint32_t GetStringOffset() const { 137 return str_offset_; 138 } 139 GetNextPosDelta(uint32_t mask_bits)140 uint32_t GetNextPosDelta(uint32_t mask_bits) const { 141 return data_ & GetMask(mask_bits); 142 } 143 GetClassDefIdx(uint32_t mask_bits)144 uint32_t GetClassDefIdx(uint32_t mask_bits) const { 145 return (data_ >> mask_bits) & GetMask(mask_bits); 146 } 147 GetHashBits(uint32_t mask_bits)148 uint32_t GetHashBits(uint32_t mask_bits) const { 149 DCHECK_LE(mask_bits, 16u); 150 return static_cast<uint64_t>(data_) >> (2u * mask_bits); 151 } 152 GetMask(uint32_t mask_bits)153 static uint32_t GetMask(uint32_t mask_bits) { 154 DCHECK_LE(mask_bits, 16u); 155 return ~(std::numeric_limits<uint32_t>::max() << mask_bits); 156 } 157 158 private: 159 uint32_t str_offset_; 160 uint32_t data_; 161 }; 162 163 static uint32_t CalculateMaskBits(uint32_t num_class_defs); 164 static bool SupportedSize(uint32_t num_class_defs); 165 166 // Construct the TypeLookupTable. 167 TypeLookupTable(const uint8_t* dex_data_pointer, 168 uint32_t mask_bits, 169 const Entry* entries, 170 std::unique_ptr<Entry[]> owned_entries); 171 172 const char* GetStringData(const Entry& entry) const; 173 174 const uint8_t* dex_data_begin_; 175 uint32_t mask_bits_; 176 const Entry* entries_; 177 // `owned_entries_` is either null (not owning `entries_`) or same pointer as `entries_`. 178 std::unique_ptr<Entry[]> owned_entries_; 179 }; 180 181 } // namespace art 182 183 #endif // ART_LIBDEXFILE_DEX_TYPE_LOOKUP_TABLE_H_ 184