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(uint32_t num_class_defs) { 42 return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) * sizeof(Entry) : 0u; 43 } 44 45 uint32_t TypeLookupTable::CalculateMask(uint32_t num_class_defs) { 46 return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) - 1u : 0u; 47 } 48 49 bool TypeLookupTable::SupportedSize(uint32_t num_class_defs) { 50 return num_class_defs != 0u && num_class_defs <= std::numeric_limits<uint16_t>::max(); 51 } 52 53 std::unique_ptr<TypeLookupTable> TypeLookupTable::Create(const DexFile& dex_file, 54 uint8_t* storage) { 55 const uint32_t num_class_defs = dex_file.NumClassDefs(); 56 return std::unique_ptr<TypeLookupTable>(SupportedSize(num_class_defs) 57 ? new TypeLookupTable(dex_file, storage) 58 : nullptr); 59 } 60 61 std::unique_ptr<TypeLookupTable> TypeLookupTable::Open(const uint8_t* dex_file_pointer, 62 const uint8_t* raw_data, 63 uint32_t num_class_defs) { 64 return std::unique_ptr<TypeLookupTable>( 65 new TypeLookupTable(dex_file_pointer, raw_data, num_class_defs)); 66 } 67 68 TypeLookupTable::TypeLookupTable(const DexFile& dex_file, uint8_t* storage) 69 : dex_file_begin_(dex_file.Begin()), 70 raw_data_length_(RawDataLength(dex_file.NumClassDefs())), 71 mask_(CalculateMask(dex_file.NumClassDefs())), 72 entries_(storage != nullptr ? reinterpret_cast<Entry*>(storage) : new Entry[mask_ + 1]), 73 owns_entries_(storage == nullptr) { 74 static_assert(alignof(Entry) == 4u, "Expecting Entry to be 4-byte aligned."); 75 DCHECK_ALIGNED(storage, alignof(Entry)); 76 std::vector<uint16_t> conflict_class_defs; 77 // The first stage. Put elements on their initial positions. If an initial position is already 78 // occupied then delay the insertion of the element to the second stage to reduce probing 79 // distance. 80 for (size_t i = 0; i < dex_file.NumClassDefs(); ++i) { 81 const DexFile::ClassDef& class_def = dex_file.GetClassDef(i); 82 const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_); 83 const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_); 84 const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id)); 85 Entry entry; 86 entry.str_offset = str_id.string_data_off_; 87 entry.data = MakeData(i, hash, GetSizeMask()); 88 if (!SetOnInitialPos(entry, hash)) { 89 conflict_class_defs.push_back(i); 90 } 91 } 92 // The second stage. The initial position of these elements had a collision. Put these elements 93 // into the nearest free cells and link them together by updating next_pos_delta. 94 for (uint16_t class_def_idx : conflict_class_defs) { 95 const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_idx); 96 const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_); 97 const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_); 98 const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id)); 99 Entry entry; 100 entry.str_offset = str_id.string_data_off_; 101 entry.data = MakeData(class_def_idx, hash, GetSizeMask()); 102 Insert(entry, hash); 103 } 104 } 105 106 TypeLookupTable::TypeLookupTable(const uint8_t* dex_file_pointer, 107 const uint8_t* raw_data, 108 uint32_t num_class_defs) 109 : dex_file_begin_(dex_file_pointer), 110 raw_data_length_(RawDataLength(num_class_defs)), 111 mask_(CalculateMask(num_class_defs)), 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
