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 "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.
     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
     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.
     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.
     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 
    105     Entry() : str_offset(0), data(0), next_pos_delta(0) {}
    106 
    107     bool IsEmpty() const {
    108       return str_offset == 0;
    109     }
    110 
    111     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 
    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
    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 
    143   uint32_t GetClassDefIdx(uint32_t data) const {
    144     return data & mask_;
    145   }
    146 
    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