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 #include "type_lookup_table.h" 18 19 #include "base/bit_utils.h" 20 #include "dex_file-inl.h" 21 #include "utf-inl.h" 22 #include "utils.h" 23 24 #include <memory> 25 #include <cstring> 26 27 namespace art { 28 29 static uint16_t MakeData(uint16_t class_def_idx, uint32_t hash, uint32_t mask) { 30 uint16_t hash_mask = static_cast<uint16_t>(~mask); 31 return (static_cast<uint16_t>(hash) & hash_mask) | class_def_idx; 32 } 33 34 TypeLookupTable::~TypeLookupTable() { 35 if (!owns_entries_) { 36 // We don't actually own the entries, don't let the unique_ptr release them. 37 entries_.release(); 38 } 39 } 40 41 uint32_t TypeLookupTable::RawDataLength() const { 42 return RawDataLength(dex_file_); 43 } 44 45 uint32_t TypeLookupTable::RawDataLength(const DexFile& dex_file) { 46 return RawDataLength(dex_file.NumClassDefs()); 47 } 48 49 uint32_t TypeLookupTable::RawDataLength(uint32_t num_class_defs) { 50 return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) * sizeof(Entry) : 0u; 51 } 52 53 uint32_t TypeLookupTable::CalculateMask(uint32_t num_class_defs) { 54 return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) - 1u : 0u; 55 } 56 57 bool TypeLookupTable::SupportedSize(uint32_t num_class_defs) { 58 return num_class_defs != 0u && num_class_defs <= std::numeric_limits<uint16_t>::max(); 59 } 60 61 TypeLookupTable* TypeLookupTable::Create(const DexFile& dex_file, uint8_t* storage) { 62 const uint32_t num_class_defs = dex_file.NumClassDefs(); 63 return SupportedSize(num_class_defs) 64 ? new TypeLookupTable(dex_file, storage) 65 : nullptr; 66 } 67 68 TypeLookupTable* TypeLookupTable::Open(const uint8_t* raw_data, const DexFile& dex_file) { 69 return new TypeLookupTable(raw_data, dex_file); 70 } 71 72 TypeLookupTable::TypeLookupTable(const DexFile& dex_file, uint8_t* storage) 73 : dex_file_(dex_file), 74 mask_(CalculateMask(dex_file.NumClassDefs())), 75 entries_(storage != nullptr ? reinterpret_cast<Entry*>(storage) : new Entry[mask_ + 1]), 76 owns_entries_(storage == nullptr) { 77 static_assert(alignof(Entry) == 4u, "Expecting Entry to be 4-byte aligned."); 78 DCHECK_ALIGNED(storage, alignof(Entry)); 79 std::vector<uint16_t> conflict_class_defs; 80 // The first stage. Put elements on their initial positions. If an initial position is already 81 // occupied then delay the insertion of the element to the second stage to reduce probing 82 // distance. 83 for (size_t i = 0; i < dex_file.NumClassDefs(); ++i) { 84 const DexFile::ClassDef& class_def = dex_file.GetClassDef(i); 85 const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_); 86 const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_); 87 const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id)); 88 Entry entry; 89 entry.str_offset = str_id.string_data_off_; 90 entry.data = MakeData(i, hash, GetSizeMask()); 91 if (!SetOnInitialPos(entry, hash)) { 92 conflict_class_defs.push_back(i); 93 } 94 } 95 // The second stage. The initial position of these elements had a collision. Put these elements 96 // into the nearest free cells and link them together by updating next_pos_delta. 97 for (uint16_t class_def_idx : conflict_class_defs) { 98 const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_idx); 99 const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_); 100 const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_); 101 const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id)); 102 Entry entry; 103 entry.str_offset = str_id.string_data_off_; 104 entry.data = MakeData(class_def_idx, hash, GetSizeMask()); 105 Insert(entry, hash); 106 } 107 } 108 109 TypeLookupTable::TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file) 110 : dex_file_(dex_file), 111 mask_(CalculateMask(dex_file.NumClassDefs())), 112 entries_(reinterpret_cast<Entry*>(const_cast<uint8_t*>(raw_data))), 113 owns_entries_(false) {} 114 115 bool TypeLookupTable::SetOnInitialPos(const Entry& entry, uint32_t hash) { 116 const uint32_t pos = hash & GetSizeMask(); 117 if (!entries_[pos].IsEmpty()) { 118 return false; 119 } 120 entries_[pos] = entry; 121 entries_[pos].next_pos_delta = 0; 122 return true; 123 } 124 125 void TypeLookupTable::Insert(const Entry& entry, uint32_t hash) { 126 uint32_t pos = FindLastEntryInBucket(hash & GetSizeMask()); 127 uint32_t next_pos = (pos + 1) & GetSizeMask(); 128 while (!entries_[next_pos].IsEmpty()) { 129 next_pos = (next_pos + 1) & GetSizeMask(); 130 } 131 const uint32_t delta = (next_pos >= pos) ? (next_pos - pos) : (next_pos + Size() - pos); 132 entries_[pos].next_pos_delta = delta; 133 entries_[next_pos] = entry; 134 entries_[next_pos].next_pos_delta = 0; 135 } 136 137 uint32_t TypeLookupTable::FindLastEntryInBucket(uint32_t pos) const { 138 const Entry* entry = &entries_[pos]; 139 while (!entry->IsLast()) { 140 pos = (pos + entry->next_pos_delta) & GetSizeMask(); 141 entry = &entries_[pos]; 142 } 143 return pos; 144 } 145 146 } // namespace art 147