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 <cstring>
20 #include <memory>
21
22 #include "base/bit_utils.h"
23 #include "base/leb128.h"
24 #include "dex/dex_file-inl.h"
25 #include "dex/utf-inl.h"
26
27 namespace art {
28
Create(const DexFile & dex_file)29 TypeLookupTable TypeLookupTable::Create(const DexFile& dex_file) {
30 uint32_t num_class_defs = dex_file.NumClassDefs();
31 if (UNLIKELY(!SupportedSize(num_class_defs))) {
32 return TypeLookupTable();
33 }
34 size_t mask_bits = CalculateMaskBits(num_class_defs);
35 size_t size = 1u << mask_bits;
36 std::unique_ptr<Entry[]> owned_entries(new Entry[size]);
37 Entry* entries = owned_entries.get();
38
39 static_assert(alignof(Entry) == 4u, "Expecting Entry to be 4-byte aligned.");
40 const uint32_t mask = Entry::GetMask(mask_bits);
41 std::vector<uint16_t> conflict_class_defs;
42 // The first stage. Put elements on their initial positions. If an initial position is already
43 // occupied then delay the insertion of the element to the second stage to reduce probing
44 // distance.
45 for (size_t class_def_idx = 0; class_def_idx < dex_file.NumClassDefs(); ++class_def_idx) {
46 const dex::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
47 const dex::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
48 const dex::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
49 const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringView(str_id));
50 const uint32_t pos = hash & mask;
51 if (entries[pos].IsEmpty()) {
52 entries[pos] = Entry(str_id.string_data_off_, hash, class_def_idx, mask_bits);
53 DCHECK(entries[pos].IsLast(mask_bits));
54 } else {
55 conflict_class_defs.push_back(class_def_idx);
56 }
57 }
58 // The second stage. The initial position of these elements had a collision. Put these elements
59 // into the nearest free cells and link them together by updating next_pos_delta.
60 for (uint16_t class_def_idx : conflict_class_defs) {
61 const dex::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
62 const dex::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
63 const dex::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
64 const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringView(str_id));
65 // Find the last entry in the chain.
66 uint32_t tail_pos = hash & mask;
67 DCHECK(!entries[tail_pos].IsEmpty());
68 while (!entries[tail_pos].IsLast(mask_bits)) {
69 tail_pos = (tail_pos + entries[tail_pos].GetNextPosDelta(mask_bits)) & mask;
70 DCHECK(!entries[tail_pos].IsEmpty());
71 }
72 // Find an empty entry for insertion.
73 uint32_t insert_pos = tail_pos;
74 do {
75 insert_pos = (insert_pos + 1) & mask;
76 } while (!entries[insert_pos].IsEmpty());
77 // Insert and chain the new entry.
78 entries[insert_pos] = Entry(str_id.string_data_off_, hash, class_def_idx, mask_bits);
79 entries[tail_pos].SetNextPosDelta((insert_pos - tail_pos) & mask, mask_bits);
80 DCHECK(entries[insert_pos].IsLast(mask_bits));
81 DCHECK(!entries[tail_pos].IsLast(mask_bits));
82 }
83
84 return TypeLookupTable(dex_file.DataBegin(), mask_bits, entries, std::move(owned_entries));
85 }
86
Open(const uint8_t * dex_data_pointer,const uint8_t * raw_data,uint32_t num_class_defs)87 TypeLookupTable TypeLookupTable::Open(const uint8_t* dex_data_pointer,
88 const uint8_t* raw_data,
89 uint32_t num_class_defs) {
90 DCHECK_ALIGNED(raw_data, alignof(Entry));
91 const Entry* entries = reinterpret_cast<const Entry*>(raw_data);
92 size_t mask_bits = CalculateMaskBits(num_class_defs);
93 return TypeLookupTable(dex_data_pointer, mask_bits, entries, /* owned_entries= */ nullptr);
94 }
95
Lookup(std::string_view str,uint32_t hash) const96 uint32_t TypeLookupTable::Lookup(std::string_view str, uint32_t hash) const {
97 uint32_t mask = Entry::GetMask(mask_bits_);
98 uint32_t pos = hash & mask;
99 // Thanks to special insertion algorithm, the element at position pos can be empty
100 // or start of the right bucket, or anywhere in the wrong bucket's chain.
101 const Entry* entry = &entries_[pos];
102 if (entry->IsEmpty()) {
103 return dex::kDexNoIndex;
104 }
105 // Look for the partial hash match first, even if traversing the wrong bucket's chain.
106 uint32_t compared_hash_bits = static_cast<uint64_t>(hash << mask_bits_) >> (2 * mask_bits_);
107 while (compared_hash_bits != entry->GetHashBits(mask_bits_)) {
108 if (entry->IsLast(mask_bits_)) {
109 return dex::kDexNoIndex;
110 }
111 pos = (pos + entry->GetNextPosDelta(mask_bits_)) & mask;
112 entry = &entries_[pos];
113 DCHECK(!entry->IsEmpty());
114 }
115 // Found partial hash match, compare strings (expecting this to succeed).
116 const std::string_view first_checked_str = GetStringData(*entry);
117 if (str == first_checked_str) {
118 return entry->GetClassDefIdx(mask_bits_);
119 }
120 // If we're at the end of the chain, return before doing further expensive work.
121 if (entry->IsLast(mask_bits_)) {
122 return dex::kDexNoIndex;
123 }
124 // Check if we're traversing the right bucket. This is important if the compared
125 // partial hash has only a few bits (i.e. it can match frequently).
126 if (((ComputeModifiedUtf8Hash(first_checked_str) ^ hash) & mask) != 0u) {
127 return dex::kDexNoIndex; // Low hash bits mismatch.
128 }
129 // Continue looking for the string in the rest of the chain.
130 do {
131 pos = (pos + entry->GetNextPosDelta(mask_bits_)) & mask;
132 entry = &entries_[pos];
133 DCHECK(!entry->IsEmpty());
134 if (compared_hash_bits == entry->GetHashBits(mask_bits_) && str == GetStringData(*entry)) {
135 return entry->GetClassDefIdx(mask_bits_);
136 }
137 } while (!entry->IsLast(mask_bits_));
138 // Not found.
139 return dex::kDexNoIndex;
140 }
141
Dump(std::ostream & os) const142 void TypeLookupTable::Dump(std::ostream& os) const {
143 size_t size = 1u << mask_bits_;
144 for (uint32_t i = 0; i < size; i++) {
145 const Entry& entry = entries_[i];
146 if (entry.IsEmpty()) {
147 os << i << ": empty";
148 } else {
149 os << i << ": " << GetStringData(entry);
150 }
151 os << '\n';
152 }
153 }
154
RawDataLength(uint32_t num_class_defs)155 uint32_t TypeLookupTable::RawDataLength(uint32_t num_class_defs) {
156 return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) * sizeof(Entry) : 0u;
157 }
158
CalculateMaskBits(uint32_t num_class_defs)159 uint32_t TypeLookupTable::CalculateMaskBits(uint32_t num_class_defs) {
160 return SupportedSize(num_class_defs) ? MinimumBitsToStore(num_class_defs - 1u) : 0u;
161 }
162
SupportedSize(uint32_t num_class_defs)163 bool TypeLookupTable::SupportedSize(uint32_t num_class_defs) {
164 return num_class_defs != 0u && num_class_defs <= std::numeric_limits<uint16_t>::max();
165 }
166
TypeLookupTable(const uint8_t * dex_data_pointer,uint32_t mask_bits,const Entry * entries,std::unique_ptr<Entry[]> owned_entries)167 TypeLookupTable::TypeLookupTable(const uint8_t* dex_data_pointer,
168 uint32_t mask_bits,
169 const Entry* entries,
170 std::unique_ptr<Entry[]> owned_entries)
171 : dex_data_begin_(dex_data_pointer),
172 mask_bits_(mask_bits),
173 entries_(entries),
174 owned_entries_(std::move(owned_entries)) {}
175
GetStringData(const Entry & entry) const176 std::string_view TypeLookupTable::GetStringData(const Entry& entry) const {
177 DCHECK(dex_data_begin_ != nullptr);
178 const uint8_t* ptr = dex_data_begin_ + entry.GetStringOffset();
179 uint32_t utf16_length = DecodeUnsignedLeb128(&ptr);
180 return DexFile::StringViewFromUtf16Length(reinterpret_cast<const char*>(ptr), utf16_length);
181 }
182
183 } // namespace art
184