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 #include "type_lookup_table.h"
     18 
     19 #include "base/bit_utils.h"
     20 #include "dex_file-inl.h"
     21 #include "utf-inl.h"
     22 #include "utils.h"
     23 
     24 #include <memory>
     25 #include <cstring>
     26 
     27 namespace art {
     28 
     29 static uint16_t MakeData(uint16_t class_def_idx, uint32_t hash, uint32_t mask) {
     30   uint16_t hash_mask = static_cast<uint16_t>(~mask);
     31   return (static_cast<uint16_t>(hash) & hash_mask) | class_def_idx;
     32 }
     33 
     34 TypeLookupTable::~TypeLookupTable() {
     35   if (!owns_entries_) {
     36     // We don't actually own the entries, don't let the unique_ptr release them.
     37     entries_.release();
     38   }
     39 }
     40 
     41 uint32_t TypeLookupTable::RawDataLength() const {
     42   return RawDataLength(dex_file_);
     43 }
     44 
     45 uint32_t TypeLookupTable::RawDataLength(const DexFile& dex_file) {
     46   return RawDataLength(dex_file.NumClassDefs());
     47 }
     48 
     49 uint32_t TypeLookupTable::RawDataLength(uint32_t num_class_defs) {
     50   return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) * sizeof(Entry) : 0u;
     51 }
     52 
     53 uint32_t TypeLookupTable::CalculateMask(uint32_t num_class_defs) {
     54   return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) - 1u : 0u;
     55 }
     56 
     57 bool TypeLookupTable::SupportedSize(uint32_t num_class_defs) {
     58   return num_class_defs != 0u && num_class_defs <= std::numeric_limits<uint16_t>::max();
     59 }
     60 
     61 TypeLookupTable* TypeLookupTable::Create(const DexFile& dex_file, uint8_t* storage) {
     62   const uint32_t num_class_defs = dex_file.NumClassDefs();
     63   return SupportedSize(num_class_defs)
     64       ? new TypeLookupTable(dex_file, storage)
     65       : nullptr;
     66 }
     67 
     68 TypeLookupTable* TypeLookupTable::Open(const uint8_t* raw_data, const DexFile& dex_file) {
     69   return new TypeLookupTable(raw_data, dex_file);
     70 }
     71 
     72 TypeLookupTable::TypeLookupTable(const DexFile& dex_file, uint8_t* storage)
     73     : dex_file_(dex_file),
     74       mask_(CalculateMask(dex_file.NumClassDefs())),
     75       entries_(storage != nullptr ? reinterpret_cast<Entry*>(storage) : new Entry[mask_ + 1]),
     76       owns_entries_(storage == nullptr) {
     77   static_assert(alignof(Entry) == 4u, "Expecting Entry to be 4-byte aligned.");
     78   DCHECK_ALIGNED(storage, alignof(Entry));
     79   std::vector<uint16_t> conflict_class_defs;
     80   // The first stage. Put elements on their initial positions. If an initial position is already
     81   // occupied then delay the insertion of the element to the second stage to reduce probing
     82   // distance.
     83   for (size_t i = 0; i < dex_file.NumClassDefs(); ++i) {
     84     const DexFile::ClassDef& class_def = dex_file.GetClassDef(i);
     85     const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
     86     const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
     87     const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
     88     Entry entry;
     89     entry.str_offset = str_id.string_data_off_;
     90     entry.data = MakeData(i, hash, GetSizeMask());
     91     if (!SetOnInitialPos(entry, hash)) {
     92       conflict_class_defs.push_back(i);
     93     }
     94   }
     95   // The second stage. The initial position of these elements had a collision. Put these elements
     96   // into the nearest free cells and link them together by updating next_pos_delta.
     97   for (uint16_t class_def_idx : conflict_class_defs) {
     98     const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
     99     const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
    100     const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
    101     const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
    102     Entry entry;
    103     entry.str_offset = str_id.string_data_off_;
    104     entry.data = MakeData(class_def_idx, hash, GetSizeMask());
    105     Insert(entry, hash);
    106   }
    107 }
    108 
    109 TypeLookupTable::TypeLookupTable(const uint8_t* raw_data, const DexFile& dex_file)
    110     : dex_file_(dex_file),
    111       mask_(CalculateMask(dex_file.NumClassDefs())),
    112       entries_(reinterpret_cast<Entry*>(const_cast<uint8_t*>(raw_data))),
    113       owns_entries_(false) {}
    114 
    115 bool TypeLookupTable::SetOnInitialPos(const Entry& entry, uint32_t hash) {
    116   const uint32_t pos = hash & GetSizeMask();
    117   if (!entries_[pos].IsEmpty()) {
    118     return false;
    119   }
    120   entries_[pos] = entry;
    121   entries_[pos].next_pos_delta = 0;
    122   return true;
    123 }
    124 
    125 void TypeLookupTable::Insert(const Entry& entry, uint32_t hash) {
    126   uint32_t pos = FindLastEntryInBucket(hash & GetSizeMask());
    127   uint32_t next_pos = (pos + 1) & GetSizeMask();
    128   while (!entries_[next_pos].IsEmpty()) {
    129     next_pos = (next_pos + 1) & GetSizeMask();
    130   }
    131   const uint32_t delta = (next_pos >= pos) ? (next_pos - pos) : (next_pos + Size() - pos);
    132   entries_[pos].next_pos_delta = delta;
    133   entries_[next_pos] = entry;
    134   entries_[next_pos].next_pos_delta = 0;
    135 }
    136 
    137 uint32_t TypeLookupTable::FindLastEntryInBucket(uint32_t pos) const {
    138   const Entry* entry = &entries_[pos];
    139   while (!entry->IsLast()) {
    140     pos = (pos + entry->next_pos_delta) & GetSizeMask();
    141     entry = &entries_[pos];
    142   }
    143   return pos;
    144 }
    145 
    146 }  // namespace art
    147