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 
MakeData(uint16_t class_def_idx,uint32_t hash,uint32_t mask)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 
~TypeLookupTable()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 
RawDataLength(uint32_t num_class_defs)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 
CalculateMask(uint32_t num_class_defs)45 uint32_t TypeLookupTable::CalculateMask(uint32_t num_class_defs) {
46   return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) - 1u : 0u;
47 }
48 
SupportedSize(uint32_t num_class_defs)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 
Create(const DexFile & dex_file,uint8_t * storage)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 
Open(const uint8_t * dex_file_pointer,const uint8_t * raw_data,uint32_t num_class_defs)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 
TypeLookupTable(const DexFile & dex_file,uint8_t * storage)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 
TypeLookupTable(const uint8_t * dex_file_pointer,const uint8_t * raw_data,uint32_t num_class_defs)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 
SetOnInitialPos(const Entry & entry,uint32_t hash)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 
Insert(const Entry & entry,uint32_t hash)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 
FindLastEntryInBucket(uint32_t pos) const137 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