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_LIBDEXFILE_DEX_TYPE_LOOKUP_TABLE_H_
18 #define ART_LIBDEXFILE_DEX_TYPE_LOOKUP_TABLE_H_
19 
20 #include <android-base/logging.h>
21 
22 #include "dex/dex_file_types.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   // Method creates lookup table for dex file.
38   static TypeLookupTable Create(const DexFile& dex_file);
39 
40   // Method opens lookup table from binary data. Lookups will traverse strings and other
41   // data contained in dex_file as well.  Lookup table does not own raw_data or dex_file.
42   static TypeLookupTable Open(const uint8_t* dex_data_pointer,
43                               const uint8_t* raw_data,
44                               uint32_t num_class_defs);
45 
46   // Create an invalid lookup table.
TypeLookupTable()47   TypeLookupTable()
48       : dex_data_begin_(nullptr),
49         mask_bits_(0u),
50         entries_(nullptr),
51         owned_entries_(nullptr) {}
52 
53   TypeLookupTable(TypeLookupTable&& src) noexcept = default;
54   TypeLookupTable& operator=(TypeLookupTable&& src) noexcept = default;
55 
~TypeLookupTable()56   ~TypeLookupTable() {
57     // Implicit deallocation by std::unique_ptr<> destructor.
58   }
59 
60   // Returns whether the TypeLookupTable is valid.
Valid()61   bool Valid() const {
62     return entries_ != nullptr;
63   }
64 
65   // Return the number of buckets in the lookup table.
Size()66   uint32_t Size() const {
67     DCHECK(Valid());
68     return 1u << mask_bits_;
69   }
70 
71   // Method search class_def_idx by class descriptor and it's hash.
72   // If no data found then the method returns dex::kDexNoIndex.
73   uint32_t Lookup(const char* str, uint32_t hash) const;
74 
75   // Method returns pointer to binary data of lookup table. Used by the oat writer.
RawData()76   const uint8_t* RawData() const {
77     DCHECK(Valid());
78     return reinterpret_cast<const uint8_t*>(entries_);
79   }
80 
81   // Method returns length of binary data. Used by the oat writer.
RawDataLength()82   uint32_t RawDataLength() const {
83     DCHECK(Valid());
84     return Size() * sizeof(Entry);
85   }
86 
87   // Method returns length of binary data for the specified number of class definitions.
88   static uint32_t RawDataLength(uint32_t num_class_defs);
89 
90  private:
91   /**
92    * To find element we need to compare strings.
93    * It is faster to compare first hashes and then strings itself.
94    * But we have no full hash of element of table. But we can use 2 ideas.
95    * 1. All minor bits of hash inside one bucket are equal.
96    *    (TODO: We're not actually using this, are we?)
97    * 2. If the dex file contains N classes and the size of the hash table is 2^n (where N <= 2^n)
98    *    then we need n bits for the class def index and n bits for the next position delta.
99    *    So we can encode part of element's hash into the remaining 32-2*n (n <= 16) bits which
100    *    would be otherwise wasted as a padding.
101    * So hash of element can be divided on three parts:
102    *     XXXX XXXX XXXY YYYY YYYY YZZZ ZZZZ ZZZZ  (example with n=11)
103    *     Z - a part of hash encoded implicitly in the bucket index
104    *         (these bits are same for all elements in bucket)
105    *     Y - a part of hash that we can write into free 32-2*n bits
106    *     X - a part of hash that we can't use without increasing the size of the entry
107    * So the `data` element of Entry is used to store the next position delta, class_def_index
108    * and a part of hash of the entry.
109    */
110   class Entry {
111    public:
Entry()112     Entry() : str_offset_(0u), data_(0u) {}
Entry(uint32_t str_offset,uint32_t hash,uint32_t class_def_index,uint32_t mask_bits)113     Entry(uint32_t str_offset, uint32_t hash, uint32_t class_def_index, uint32_t mask_bits)
114         : str_offset_(str_offset),
115           data_(((hash & ~GetMask(mask_bits)) | class_def_index) << mask_bits) {
116       DCHECK_EQ(class_def_index & ~GetMask(mask_bits), 0u);
117     }
118 
SetNextPosDelta(uint32_t next_pos_delta,uint32_t mask_bits)119     void SetNextPosDelta(uint32_t next_pos_delta, uint32_t mask_bits) {
120       DCHECK_EQ(GetNextPosDelta(mask_bits), 0u);
121       DCHECK_EQ(next_pos_delta & ~GetMask(mask_bits), 0u);
122       DCHECK_NE(next_pos_delta, 0u);
123       data_ |= next_pos_delta;
124     }
125 
IsEmpty()126     bool IsEmpty() const {
127       return str_offset_ == 0u;
128     }
129 
IsLast(uint32_t mask_bits)130     bool IsLast(uint32_t mask_bits) const {
131       return GetNextPosDelta(mask_bits) == 0u;
132     }
133 
GetStringOffset()134     uint32_t GetStringOffset() const {
135       return str_offset_;
136     }
137 
GetNextPosDelta(uint32_t mask_bits)138     uint32_t GetNextPosDelta(uint32_t mask_bits) const {
139       return data_ & GetMask(mask_bits);
140     }
141 
GetClassDefIdx(uint32_t mask_bits)142     uint32_t GetClassDefIdx(uint32_t mask_bits) const {
143       return (data_ >> mask_bits) & GetMask(mask_bits);
144     }
145 
GetHashBits(uint32_t mask_bits)146     uint32_t GetHashBits(uint32_t mask_bits) const {
147       DCHECK_LE(mask_bits, 16u);
148       return data_ >> (2u * mask_bits);
149     }
150 
GetMask(uint32_t mask_bits)151     static uint32_t GetMask(uint32_t mask_bits) {
152       DCHECK_LE(mask_bits, 16u);
153       return ~(std::numeric_limits<uint32_t>::max() << mask_bits);
154     }
155 
156    private:
157     uint32_t str_offset_;
158     uint32_t data_;
159   };
160 
161   static uint32_t CalculateMaskBits(uint32_t num_class_defs);
162   static bool SupportedSize(uint32_t num_class_defs);
163 
164   // Construct the TypeLookupTable.
165   TypeLookupTable(const uint8_t* dex_data_pointer,
166                   uint32_t mask_bits,
167                   const Entry* entries,
168                   std::unique_ptr<Entry[]> owned_entries);
169 
170   const char* GetStringData(const Entry& entry) const;
171 
172   const uint8_t* dex_data_begin_;
173   uint32_t mask_bits_;
174   const Entry* entries_;
175   // `owned_entries_` is either null (not owning `entries_`) or same pointer as `entries_`.
176   std::unique_ptr<Entry[]> owned_entries_;
177 };
178 
179 }  // namespace art
180 
181 #endif  // ART_LIBDEXFILE_DEX_TYPE_LOOKUP_TABLE_H_
182