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
27namespace art {
28
29static 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
34TypeLookupTable::~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
41uint32_t TypeLookupTable::RawDataLength() const {
42  return RawDataLength(dex_file_);
43}
44
45uint32_t TypeLookupTable::RawDataLength(const DexFile& dex_file) {
46  return RawDataLength(dex_file.NumClassDefs());
47}
48
49uint32_t TypeLookupTable::RawDataLength(uint32_t num_class_defs) {
50  return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) * sizeof(Entry) : 0u;
51}
52
53uint32_t TypeLookupTable::CalculateMask(uint32_t num_class_defs) {
54  return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) - 1u : 0u;
55}
56
57bool TypeLookupTable::SupportedSize(uint32_t num_class_defs) {
58  return num_class_defs != 0u && num_class_defs <= std::numeric_limits<uint16_t>::max();
59}
60
61TypeLookupTable* 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
68TypeLookupTable* TypeLookupTable::Open(const uint8_t* raw_data, const DexFile& dex_file) {
69  return new TypeLookupTable(raw_data, dex_file);
70}
71
72TypeLookupTable::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
109TypeLookupTable::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
115bool 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
125void 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
137uint32_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