/*
|
* 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 <cstring>
|
#include <memory>
|
|
#include "base/bit_utils.h"
|
#include "base/leb128.h"
|
#include "dex/dex_file-inl.h"
|
#include "dex/utf-inl.h"
|
|
namespace art {
|
|
static inline bool ModifiedUtf8StringEquals(const char* lhs, const char* rhs) {
|
return CompareModifiedUtf8ToModifiedUtf8AsUtf16CodePointValues(lhs, rhs) == 0;
|
}
|
|
TypeLookupTable TypeLookupTable::Create(const DexFile& dex_file) {
|
uint32_t num_class_defs = dex_file.NumClassDefs();
|
if (UNLIKELY(!SupportedSize(num_class_defs))) {
|
return TypeLookupTable();
|
}
|
size_t mask_bits = CalculateMaskBits(num_class_defs);
|
size_t size = 1u << mask_bits;
|
std::unique_ptr<Entry[]> owned_entries(new Entry[size]);
|
Entry* entries = owned_entries.get();
|
|
static_assert(alignof(Entry) == 4u, "Expecting Entry to be 4-byte aligned.");
|
const uint32_t mask = Entry::GetMask(mask_bits);
|
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 class_def_idx = 0; class_def_idx < dex_file.NumClassDefs(); ++class_def_idx) {
|
const dex::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
|
const dex::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
|
const dex::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
|
const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
|
const uint32_t pos = hash & mask;
|
if (entries[pos].IsEmpty()) {
|
entries[pos] = Entry(str_id.string_data_off_, hash, class_def_idx, mask_bits);
|
DCHECK(entries[pos].IsLast(mask_bits));
|
} else {
|
conflict_class_defs.push_back(class_def_idx);
|
}
|
}
|
// 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 dex::ClassDef& class_def = dex_file.GetClassDef(class_def_idx);
|
const dex::TypeId& type_id = dex_file.GetTypeId(class_def.class_idx_);
|
const dex::StringId& str_id = dex_file.GetStringId(type_id.descriptor_idx_);
|
const uint32_t hash = ComputeModifiedUtf8Hash(dex_file.GetStringData(str_id));
|
// Find the last entry in the chain.
|
uint32_t tail_pos = hash & mask;
|
DCHECK(!entries[tail_pos].IsEmpty());
|
while (!entries[tail_pos].IsLast(mask_bits)) {
|
tail_pos = (tail_pos + entries[tail_pos].GetNextPosDelta(mask_bits)) & mask;
|
DCHECK(!entries[tail_pos].IsEmpty());
|
}
|
// Find an empty entry for insertion.
|
uint32_t insert_pos = tail_pos;
|
do {
|
insert_pos = (insert_pos + 1) & mask;
|
} while (!entries[insert_pos].IsEmpty());
|
// Insert and chain the new entry.
|
entries[insert_pos] = Entry(str_id.string_data_off_, hash, class_def_idx, mask_bits);
|
entries[tail_pos].SetNextPosDelta((insert_pos - tail_pos) & mask, mask_bits);
|
DCHECK(entries[insert_pos].IsLast(mask_bits));
|
DCHECK(!entries[tail_pos].IsLast(mask_bits));
|
}
|
|
return TypeLookupTable(dex_file.DataBegin(), mask_bits, entries, std::move(owned_entries));
|
}
|
|
TypeLookupTable TypeLookupTable::Open(const uint8_t* dex_data_pointer,
|
const uint8_t* raw_data,
|
uint32_t num_class_defs) {
|
DCHECK_ALIGNED(raw_data, alignof(Entry));
|
const Entry* entries = reinterpret_cast<const Entry*>(raw_data);
|
size_t mask_bits = CalculateMaskBits(num_class_defs);
|
return TypeLookupTable(dex_data_pointer, mask_bits, entries, /* owned_entries= */ nullptr);
|
}
|
|
uint32_t TypeLookupTable::Lookup(const char* str, uint32_t hash) const {
|
uint32_t mask = Entry::GetMask(mask_bits_);
|
uint32_t pos = hash & mask;
|
// Thanks to special insertion algorithm, the element at position pos can be empty
|
// or start of the right bucket, or anywhere in the wrong bucket's chain.
|
const Entry* entry = &entries_[pos];
|
if (entry->IsEmpty()) {
|
return dex::kDexNoIndex;
|
}
|
// Look for the partial hash match first, even if traversing the wrong bucket's chain.
|
uint32_t compared_hash_bits = (hash << mask_bits_) >> (2 * mask_bits_);
|
while (compared_hash_bits != entry->GetHashBits(mask_bits_)) {
|
if (entry->IsLast(mask_bits_)) {
|
return dex::kDexNoIndex;
|
}
|
pos = (pos + entry->GetNextPosDelta(mask_bits_)) & mask;
|
entry = &entries_[pos];
|
DCHECK(!entry->IsEmpty());
|
}
|
// Found partial hash match, compare strings (expecting this to succeed).
|
const char* first_checked_str = GetStringData(*entry);
|
if (ModifiedUtf8StringEquals(str, first_checked_str)) {
|
return entry->GetClassDefIdx(mask_bits_);
|
}
|
// If we're at the end of the chain, return before doing further expensive work.
|
if (entry->IsLast(mask_bits_)) {
|
return dex::kDexNoIndex;
|
}
|
// Check if we're traversing the right bucket. This is important if the compared
|
// partial hash has only a few bits (i.e. it can match frequently).
|
if (((ComputeModifiedUtf8Hash(first_checked_str) ^ hash) & mask) != 0u) {
|
return dex::kDexNoIndex; // Low hash bits mismatch.
|
}
|
// Continue looking for the string in the rest of the chain.
|
do {
|
pos = (pos + entry->GetNextPosDelta(mask_bits_)) & mask;
|
entry = &entries_[pos];
|
DCHECK(!entry->IsEmpty());
|
if (compared_hash_bits == entry->GetHashBits(mask_bits_) &&
|
ModifiedUtf8StringEquals(str, GetStringData(*entry))) {
|
return entry->GetClassDefIdx(mask_bits_);
|
}
|
} while (!entry->IsLast(mask_bits_));
|
// Not found.
|
return dex::kDexNoIndex;
|
}
|
|
uint32_t TypeLookupTable::RawDataLength(uint32_t num_class_defs) {
|
return SupportedSize(num_class_defs) ? RoundUpToPowerOfTwo(num_class_defs) * sizeof(Entry) : 0u;
|
}
|
|
uint32_t TypeLookupTable::CalculateMaskBits(uint32_t num_class_defs) {
|
return SupportedSize(num_class_defs) ? MinimumBitsToStore(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();
|
}
|
|
TypeLookupTable::TypeLookupTable(const uint8_t* dex_data_pointer,
|
uint32_t mask_bits,
|
const Entry* entries,
|
std::unique_ptr<Entry[]> owned_entries)
|
: dex_data_begin_(dex_data_pointer),
|
mask_bits_(mask_bits),
|
entries_(entries),
|
owned_entries_(std::move(owned_entries)) {}
|
|
const char* TypeLookupTable::GetStringData(const Entry& entry) const {
|
DCHECK(dex_data_begin_ != nullptr);
|
const uint8_t* ptr = dex_data_begin_ + entry.GetStringOffset();
|
// Skip string length.
|
DecodeUnsignedLeb128(&ptr);
|
return reinterpret_cast<const char*>(ptr);
|
}
|
|
} // namespace art
|
