1d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko/* 2d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * Copyright (C) 2015 The Android Open Source Project 3d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * 4d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * Licensed under the Apache License, Version 2.0 (the "License"); 5d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * you may not use this file except in compliance with the License. 6d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * You may obtain a copy of the License at 7d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * 8d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * http://www.apache.org/licenses/LICENSE-2.0 9d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * 10d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * Unless required by applicable law or agreed to in writing, software 11d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * distributed under the License is distributed on an "AS IS" BASIS, 12d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * See the License for the specific language governing permissions and 14d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * limitations under the License. 15d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko */ 16d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 17d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko#ifndef ART_RUNTIME_TYPE_LOOKUP_TABLE_H_ 18d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko#define ART_RUNTIME_TYPE_LOOKUP_TABLE_H_ 19d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 20d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko#include "dex_file.h" 21d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko#include "leb128.h" 22d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko#include "utf.h" 23d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 24d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenkonamespace art { 25d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 26d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko/** 27d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * TypeLookupTable used to find class_def_idx by class descriptor quickly. 28d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * Implementation of TypeLookupTable is based on hash table. 29d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * This class instantiated at compile time by calling Create() method and written into OAT file. 30d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * At runtime, the raw data is read from memory-mapped file by calling Open() method. The table 31d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * memory remains clean. 32d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko */ 33d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenkoclass TypeLookupTable { 34d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko public: 35d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko ~TypeLookupTable(); 36d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 37d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Return the number of buckets in the lookup table. 38d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko uint32_t Size() const { 39d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return mask_ + 1; 40d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 41d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 42d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Method search class_def_idx by class descriptor and it's hash. 43d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // If no data found then the method returns DexFile::kDexNoIndex 44d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko ALWAYS_INLINE uint32_t Lookup(const char* str, uint32_t hash) const { 45d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko uint32_t pos = hash & GetSizeMask(); 46d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Thanks to special insertion algorithm, the element at position pos can be empty or start of 47d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // bucket. 48d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko const Entry* entry = &entries_[pos]; 49d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko while (!entry->IsEmpty()) { 50d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko if (CmpHashBits(entry->data, hash) && IsStringsEquals(str, entry->str_offset)) { 51d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return GetClassDefIdx(entry->data); 52d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 53d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko if (entry->IsLast()) { 54d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return DexFile::kDexNoIndex; 55d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 56d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko pos = (pos + entry->next_pos_delta) & GetSizeMask(); 57d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko entry = &entries_[pos]; 58d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 59d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return DexFile::kDexNoIndex; 60d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 61d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 62d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Method creates lookup table for dex file 639bdf108885a27ba05fae8501725649574d7c491bVladimir Marko static TypeLookupTable* Create(const DexFile& dex_file, uint8_t* storage = nullptr); 64d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 65d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Method opens lookup table from binary data. Lookup table does not owns binary data. 66d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko static TypeLookupTable* Open(const uint8_t* raw_data, const DexFile& dex_file); 67d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 68d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Method returns pointer to binary data of lookup table. Used by the oat writer. 69d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko const uint8_t* RawData() const { 70d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return reinterpret_cast<const uint8_t*>(entries_.get()); 71d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 72d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 73d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Method returns length of binary data. Used by the oat writer. 74d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko uint32_t RawDataLength() const; 75d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 76d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Method returns length of binary data for the specified dex file. 77d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko static uint32_t RawDataLength(const DexFile& dex_file); 78d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 799bdf108885a27ba05fae8501725649574d7c491bVladimir Marko // Method returns length of binary data for the specified number of class definitions. 809bdf108885a27ba05fae8501725649574d7c491bVladimir Marko static uint32_t RawDataLength(uint32_t num_class_defs); 819bdf108885a27ba05fae8501725649574d7c491bVladimir Marko 82d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko private: 83d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko /** 84d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * To find element we need to compare strings. 85d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * It is faster to compare first hashes and then strings itself. 86d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * But we have no full hash of element of table. But we can use 2 ideas. 87d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * 1. All minor bits of hash inside one bucket are equals. 88d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * 2. If dex file contains N classes and size of hash table is 2^n (where N <= 2^n) 89d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * then 16-n bits are free. So we can encode part of element's hash into these bits. 90d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * So hash of element can be divided on three parts: 91d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * XXXX XXXX XXXX YYYY YZZZ ZZZZ ZZZZZ 92d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * Z - a part of hash encoded in bucket (these bits of has are same for all elements in bucket) - 93d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * n bits 94d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * Y - a part of hash that we can write into free 16-n bits (because only n bits used to store 95d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * class_def_idx) 96d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * X - a part of has that we can't use without increasing increase 97d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko * So the data element of Entry used to store class_def_idx and part of hash of the entry. 98d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko */ 99d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko struct Entry { 100d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko uint32_t str_offset; 101d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko uint16_t data; 102d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko uint16_t next_pos_delta; 103d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 104d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko Entry() : str_offset(0), data(0), next_pos_delta(0) {} 105d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 106d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko bool IsEmpty() const { 107d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return str_offset == 0; 108d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 109d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 110d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko bool IsLast() const { 111d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return next_pos_delta == 0; 112d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 113d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko }; 114d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 1159bdf108885a27ba05fae8501725649574d7c491bVladimir Marko static uint32_t CalculateMask(uint32_t num_class_defs); 1169bdf108885a27ba05fae8501725649574d7c491bVladimir Marko static bool SupportedSize(uint32_t num_class_defs); 1179bdf108885a27ba05fae8501725649574d7c491bVladimir Marko 118d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Construct from a dex file. 1199bdf108885a27ba05fae8501725649574d7c491bVladimir Marko explicit TypeLookupTable(const DexFile& dex_file, uint8_t* storage); 120d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 121d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Construct from a dex file with existing data. 122d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file); 123d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 124d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko bool IsStringsEquals(const char* str, uint32_t str_offset) const { 125d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko const uint8_t* ptr = dex_file_.Begin() + str_offset; 126d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Skip string length. 127d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko DecodeUnsignedLeb128(&ptr); 128d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues( 129d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko str, reinterpret_cast<const char*>(ptr)) == 0; 130d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 131d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 132d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Method extracts hash bits from element's data and compare them with 133d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // the corresponding bits of the specified hash 134d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko bool CmpHashBits(uint32_t data, uint32_t hash) const { 135d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko uint32_t mask = static_cast<uint16_t>(~GetSizeMask()); 136d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return (hash & mask) == (data & mask); 137d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 138d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 139d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko uint32_t GetClassDefIdx(uint32_t data) const { 140d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return data & mask_; 141d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 142d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 143d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko uint32_t GetSizeMask() const { 144d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko return mask_; 145d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko } 146d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 147d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Attempt to set an entry on it's hash' slot. If there is alrady something there, return false. 148d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Otherwise return true. 149d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko bool SetOnInitialPos(const Entry& entry, uint32_t hash); 150d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 151d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Insert an entry, probes until there is an empty slot. 152d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko void Insert(const Entry& entry, uint32_t hash); 153d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 154d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // Find the last entry in a chain. 155d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko uint32_t FindLastEntryInBucket(uint32_t cur_pos) const; 156d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 157d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko const DexFile& dex_file_; 158d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko const uint32_t mask_; 159d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko std::unique_ptr<Entry[]> entries_; 160d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko // owns_entries_ specifies if the lookup table owns the entries_ array. 161d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko const bool owns_entries_; 162d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 163d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko DISALLOW_IMPLICIT_CONSTRUCTORS(TypeLookupTable); 164d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko}; 165d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 166d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko} // namespace art 167d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko 168d9786b0e5be23ea0258405165098b4216579209cArtem Udovichenko#endif // ART_RUNTIME_TYPE_LOOKUP_TABLE_H_ 169