Home | History | Annotate | Download | only in runtime 
      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.
     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