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 
24 namespace art {
25 
26 class 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  */
35 class TypeLookupTable {
36  public:
37   ~TypeLookupTable();
38 
39   // Return the number of buckets in the lookup table.
Size()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.
Lookup(const char * str,uint32_t hash)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.
RawData()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.
RawDataLength()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 
EntryEntry107     Entry() : str_offset(0), data(0), next_pos_delta(0) {}
108 
IsEmptyEntry109     bool IsEmpty() const {
110       return str_offset == 0;
111     }
112 
IsLastEntry113     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 
IsStringsEquals(const char * str,uint32_t str_offset)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
CmpHashBits(uint32_t data,uint32_t 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 
GetClassDefIdx(uint32_t data)145   uint32_t GetClassDefIdx(uint32_t data) const {
146     return data & mask_;
147   }
148 
GetSizeMask()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