runtime/type_lookup_table.cc

/*
 * Copyright (C) 2015 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "type_lookup_table.h"

#include "base/bit_utils.h"
#include "dex_file-inl.h"
#include "utf-inl.h"
#include "utils.h"

#include <memory>
#include <cstring>

namespace art {

static uint16_t MakeData(uint16_t class_def_idx, uint32_t hash, uint32_t mask) {
  uint16_t hash_mask = static_cast<uint16_t>(~mask);
  return (static_cast<uint16_t>(hash) & hash_mask) | class_def_idx;
}

TypeLookupTable::~TypeLookupTable() {
  if (!owns_entries_) {
    // We don't actually own the entries, don't let the unique_ptr release them.
    entries_.release();
  }
}

uint32_t TypeLookupTable::RawDataLength(uint32_t num_class_defs) {
  return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) * sizeof(Entry) : 0u;
}

uint32_t TypeLookupTable::CalculateMask(uint32_t num_class_defs) {
  return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) - 1u : 0u;
}

bool TypeLookupTable::SupportedSize(uint32_t num_class_defs) {
  return num_class_defs != 0u && num_class_defs <= std::numeric_limits<uint16_t>::max();
}

std::unique_ptr<TypeLookupTable> TypeLookupTable::Create(const DexFile& dex_file,
                                                         uint8_t* storage) {
  const uint32_t num_class_defs = dex_file.NumClassDefs();
  return std::unique_ptr<TypeLookupTable>(SupportedSize(num_class_defs)
      ? new TypeLookupTable(dex_file, storage)
      : nullptr);
}

std::unique_ptr<TypeLookupTable> TypeLookupTable::Open(const uint8_t* dex_file_pointer,
                                                       const uint8_t* raw_data,
                                                       uint32_t num_class_defs) {
  return std::unique_ptr<TypeLookupTable>(
      new TypeLookupTable(dex_file_pointer, raw_data, num_class_defs));
}

TypeLookupTable::TypeLookupTable(const DexFile& dex_file, uint8_t* storage)
    : dex_file_begin_(dex_file.Begin()),
      raw_data_length_(RawDataLength(dex_file.NumClassDefs())),
      mask_(CalculateMask(dex_file.NumClassDefs())),
      entries_(storage != nullptr ? reinterpret_cast<Entry*>(storage) : new Entry[mask_ + 1]),
      owns_entries_(storage == nullptr) {
  static_assert(alignof(Entry) == 4u, "Expecting Entry to be 4-byte aligned.");
  DCHECK_ALIGNED(storage, alignof(Entry));
  std::vector<uint16_t> conflict_class_defs;
  // The first stage. Put elements on their initial positions. If an initial position is already
  // occupied then delay the insertion of the element to the second stage to reduce probing
  // distance.
  for (size_t i = 0; i < dex_file.NumClassDefs(); ++i) {
    const DexFile::ClassDef& class_def = dex_file.GetClassDef(i);
    const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
    const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
    const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
    Entry entry;
    entry.str_offset = str_id.string_data_off_;
    entry.data = MakeData(i, hash, GetSizeMask());
    if (!SetOnInitialPos(entry, hash)) {
      conflict_class_defs.push_back(i);
    }
  }
  // The second stage. The initial position of these elements had a collision. Put these elements
  // into the nearest free cells and link them together by updating next_pos_delta.
  for (uint16_t class_def_idx : conflict_class_defs) {
    const DexFile::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
    const DexFile::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
    const DexFile::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
    const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
    Entry entry;
    entry.str_offset = str_id.string_data_off_;
    entry.data = MakeData(class_def_idx, hash, GetSizeMask());
    Insert(entry, hash);
  }
}

TypeLookupTable::TypeLookupTable(const uint8_t* dex_file_pointer,
                                 const uint8_t* raw_data,
                                 uint32_t num_class_defs)
    : dex_file_begin_(dex_file_pointer),
      raw_data_length_(RawDataLength(num_class_defs)),
      mask_(CalculateMask(num_class_defs)),
      entries_(reinterpret_cast<Entry*>(const_cast<uint8_t*>(raw_data))),
      owns_entries_(false) {}

bool TypeLookupTable::SetOnInitialPos(const Entry& entry, uint32_t hash) {
  const uint32_t pos = hash & GetSizeMask();
  if (!entries_[pos].IsEmpty()) {
    return false;
  }
  entries_[pos] = entry;
  entries_[pos].next_pos_delta = 0;
  return true;
}

void TypeLookupTable::Insert(const Entry& entry, uint32_t hash) {
  uint32_t pos = FindLastEntryInBucket(hash & GetSizeMask());
  uint32_t next_pos = (pos + 1) & GetSizeMask();
  while (!entries_[next_pos].IsEmpty()) {
    next_pos = (next_pos + 1) & GetSizeMask();
  }
  const uint32_t delta = (next_pos >= pos) ? (next_pos - pos) : (next_pos + Size() - pos);
  entries_[pos].next_pos_delta = delta;
  entries_[next_pos] = entry;
  entries_[next_pos].next_pos_delta = 0;
}

uint32_t TypeLookupTable::FindLastEntryInBucket(uint32_t pos) const {
  const Entry* entry = &entries_[pos];
  while (!entry->IsLast()) {
    pos = (pos + entry->next_pos_delta) & GetSizeMask();
    entry = &entries_[pos];
  }
  return pos;
}

}  // namespace art