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 private: 91 /** 92 * To find element we need to compare strings. 93 * It is faster to compare first hashes and then strings itself. 94 * But we have no full hash of element of table. But we can use 2 ideas. 95 * 1. All minor bits of hash inside one bucket are equal. 96 * (TODO: We're not actually using this, are we?) 97 * 2. If the dex file contains N classes and the size of the hash table is 2^n (where N <= 2^n) 98 * then we need n bits for the class def index and n bits for the next position delta. 99 * So we can encode part of element's hash into the remaining 32-2*n (n <= 16) bits which 100 * would be otherwise wasted as a padding. 101 * So hash of element can be divided on three parts: 102 * XXXX XXXX XXXY YYYY YYYY YZZZ ZZZZ ZZZZ (example with n=11) 103 * Z - a part of hash encoded implicitly in the bucket index 104 * (these bits are same for all elements in bucket) 105 * Y - a part of hash that we can write into free 32-2*n bits 106 * X - a part of hash that we can't use without increasing the size of the entry 107 * So the `data` element of Entry is used to store the next position delta, class_def_index 108 * and a part of hash of the entry. 109 */ 110 class Entry { 111 public: Entry()112 Entry() : str_offset_(0u), data_(0u) {} Entry(uint32_t str_offset,uint32_t hash,uint32_t class_def_index,uint32_t mask_bits)113 Entry(uint32_t str_offset, uint32_t hash, uint32_t class_def_index, uint32_t mask_bits) 114 : str_offset_(str_offset), 115 data_(((hash & ~GetMask(mask_bits)) | class_def_index) << mask_bits) { 116 DCHECK_EQ(class_def_index & ~GetMask(mask_bits), 0u); 117 } 118 SetNextPosDelta(uint32_t next_pos_delta,uint32_t mask_bits)119 void SetNextPosDelta(uint32_t next_pos_delta, uint32_t mask_bits) { 120 DCHECK_EQ(GetNextPosDelta(mask_bits), 0u); 121 DCHECK_EQ(next_pos_delta & ~GetMask(mask_bits), 0u); 122 DCHECK_NE(next_pos_delta, 0u); 123 data_ |= next_pos_delta; 124 } 125 IsEmpty()126 bool IsEmpty() const { 127 return str_offset_ == 0u; 128 } 129 IsLast(uint32_t mask_bits)130 bool IsLast(uint32_t mask_bits) const { 131 return GetNextPosDelta(mask_bits) == 0u; 132 } 133 GetStringOffset()134 uint32_t GetStringOffset() const { 135 return str_offset_; 136 } 137 GetNextPosDelta(uint32_t mask_bits)138 uint32_t GetNextPosDelta(uint32_t mask_bits) const { 139 return data_ & GetMask(mask_bits); 140 } 141 GetClassDefIdx(uint32_t mask_bits)142 uint32_t GetClassDefIdx(uint32_t mask_bits) const { 143 return (data_ >> mask_bits) & GetMask(mask_bits); 144 } 145 GetHashBits(uint32_t mask_bits)146 uint32_t GetHashBits(uint32_t mask_bits) const { 147 DCHECK_LE(mask_bits, 16u); 148 return data_ >> (2u * mask_bits); 149 } 150 GetMask(uint32_t mask_bits)151 static uint32_t GetMask(uint32_t mask_bits) { 152 DCHECK_LE(mask_bits, 16u); 153 return ~(std::numeric_limits<uint32_t>::max() << mask_bits); 154 } 155 156 private: 157 uint32_t str_offset_; 158 uint32_t data_; 159 }; 160 161 static uint32_t CalculateMaskBits(uint32_t num_class_defs); 162 static bool SupportedSize(uint32_t num_class_defs); 163 164 // Construct the TypeLookupTable. 165 TypeLookupTable(const uint8_t* dex_data_pointer, 166 uint32_t mask_bits, 167 const Entry* entries, 168 std::unique_ptr<Entry[]> owned_entries); 169 170 const char* GetStringData(const Entry& entry) const; 171 172 const uint8_t* dex_data_begin_; 173 uint32_t mask_bits_; 174 const Entry* entries_; 175 // `owned_entries_` is either null (not owning `entries_`) or same pointer as `entries_`. 176 std::unique_ptr<Entry[]> owned_entries_; 177 }; 178 179 } // namespace art 180 181 #endif // ART_LIBDEXFILE_DEX_TYPE_LOOKUP_TABLE_H_ 182