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