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#ifndef ART_RUNTIME_TYPE_LOOKUP_TABLE_H_
18#define ART_RUNTIME_TYPE_LOOKUP_TABLE_H_
19
20#include "base/leb128.h"
21#include "dex/dex_file_types.h"
22#include "dex/utf.h"
23
24namespace art {
25
26class DexFile;
27
28/**
29 * TypeLookupTable used to find class_def_idx by class descriptor quickly.
30 * Implementation of TypeLookupTable is based on hash table.
31 * This class instantiated at compile time by calling Create() method and written into OAT file.
32 * At runtime, the raw data is read from memory-mapped file by calling Open() method. The table
33 * memory remains clean.
34 */
35class TypeLookupTable {
36 public:
37  ~TypeLookupTable();
38
39  // Return the number of buckets in the lookup table.
40  uint32_t Size() const {
41    return mask_ + 1;
42  }
43
44  // Method search class_def_idx by class descriptor and it's hash.
45  // If no data found then the method returns dex::kDexNoIndex.
46  uint32_t Lookup(const char* str, uint32_t hash) const {
47    uint32_t pos = hash & GetSizeMask();
48    // Thanks to special insertion algorithm, the element at position pos can be empty or start of
49    // bucket.
50    const Entry* entry = &entries_[pos];
51    while (!entry->IsEmpty()) {
52      if (CmpHashBits(entry->data, hash) && IsStringsEquals(str, entry->str_offset)) {
53        return GetClassDefIdx(entry->data);
54      }
55      if (entry->IsLast()) {
56        return dex::kDexNoIndex;
57      }
58      pos = (pos + entry->next_pos_delta) & GetSizeMask();
59      entry = &entries_[pos];
60    }
61    return dex::kDexNoIndex;
62  }
63
64  // Method creates lookup table for dex file
65  static std::unique_ptr<TypeLookupTable> Create(const DexFile& dex_file,
66                                                 uint8_t* storage = nullptr);
67
68  // Method opens lookup table from binary data. Lookups will traverse strings and other
69  // data contained in dex_file as well.  Lookup table does not own raw_data or dex_file.
70  static std::unique_ptr<TypeLookupTable> Open(const uint8_t* dex_file_pointer,
71                                               const uint8_t* raw_data,
72                                               uint32_t num_class_defs);
73
74  // Method returns pointer to binary data of lookup table. Used by the oat writer.
75  const uint8_t* RawData() const {
76    return reinterpret_cast<const uint8_t*>(entries_.get());
77  }
78
79  // Method returns length of binary data. Used by the oat writer.
80  uint32_t RawDataLength() const { return raw_data_length_; }
81
82  // Method returns length of binary data for the specified number of class definitions.
83  static uint32_t RawDataLength(uint32_t num_class_defs);
84
85 private:
86   /**
87    * To find element we need to compare strings.
88    * It is faster to compare first hashes and then strings itself.
89    * But we have no full hash of element of table. But we can use 2 ideas.
90    * 1. All minor bits of hash inside one bucket are equals.
91    * 2. If dex file contains N classes and size of hash table is 2^n (where N <= 2^n)
92    *    then 16-n bits are free. So we can encode part of element's hash into these bits.
93    * So hash of element can be divided on three parts:
94    * XXXX XXXX XXXX YYYY YZZZ ZZZZ ZZZZZ
95    * Z - a part of hash encoded in bucket (these bits of has are same for all elements in bucket) -
96    * n bits
97    * Y - a part of hash that we can write into free 16-n bits (because only n bits used to store
98    * class_def_idx)
99    * X - a part of has that we can't use without increasing increase
100    * So the data element of Entry used to store class_def_idx and part of hash of the entry.
101    */
102  struct Entry {
103    uint32_t str_offset;
104    uint16_t data;
105    uint16_t next_pos_delta;
106
107    Entry() : str_offset(0), data(0), next_pos_delta(0) {}
108
109    bool IsEmpty() const {
110      return str_offset == 0;
111    }
112
113    bool IsLast() const {
114      return next_pos_delta == 0;
115    }
116  };
117
118  static uint32_t CalculateMask(uint32_t num_class_defs);
119  static bool SupportedSize(uint32_t num_class_defs);
120
121  // Construct from a dex file.
122  explicit TypeLookupTable(const DexFile& dex_file, uint8_t* storage);
123
124  // Construct from a dex file with existing data.
125  TypeLookupTable(const uint8_t* dex_file_pointer,
126                  const uint8_t* raw_data,
127                  uint32_t num_class_defs);
128
129  bool IsStringsEquals(const char* str, uint32_t str_offset) const {
130    const uint8_t* ptr = dex_data_begin_ + str_offset;
131    CHECK(dex_data_begin_ != nullptr);
132    // Skip string length.
133    DecodeUnsignedLeb128(&ptr);
134    return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(
135        str, reinterpret_cast<const char*>(ptr)) == 0;
136  }
137
138  // Method extracts hash bits from element's data and compare them with
139  // the corresponding bits of the specified hash
140  bool CmpHashBits(uint32_t data, uint32_t hash) const {
141    uint32_t mask = static_cast<uint16_t>(~GetSizeMask());
142    return (hash & mask) == (data & mask);
143  }
144
145  uint32_t GetClassDefIdx(uint32_t data) const {
146    return data & mask_;
147  }
148
149  uint32_t GetSizeMask() const {
150    return mask_;
151  }
152
153  // Attempt to set an entry on its hash's slot. If there is already something there, return false.
154  // Otherwise return true.
155  bool SetOnInitialPos(const Entry& entry, uint32_t hash);
156
157  // Insert an entry, probes until there is an empty slot.
158  void Insert(const Entry& entry, uint32_t hash);
159
160  // Find the last entry in a chain.
161  uint32_t FindLastEntryInBucket(uint32_t cur_pos) const;
162
163  const uint8_t* dex_data_begin_;
164  const uint32_t raw_data_length_;
165  const uint32_t mask_;
166  std::unique_ptr<Entry[]> entries_;
167  // owns_entries_ specifies if the lookup table owns the entries_ array.
168  const bool owns_entries_;
169
170  DISALLOW_IMPLICIT_CONSTRUCTORS(TypeLookupTable);
171};
172
173}  // namespace art
174
175#endif  // ART_RUNTIME_TYPE_LOOKUP_TABLE_H_
176