blob: 3d7b529f4c52205f4ee954fc65c235dc94b8b3c1 [file] [log] [blame]
// Copyright 2019 The Cobalt Authors. All Rights Reserved.
//
// 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 "starboard/elf_loader/gnu_hash_table.h"
#include <cstring>
#include "starboard/common/log.h"
#include "starboard/elf_loader/log.h"
#include "starboard/string.h"
namespace starboard {
namespace elf_loader {
// Compute the GNU hash of a given symbol.
// For more details on the hash function:
// https://blogs.oracle.com/solaris/gnu-hash-elf-sections-v2
static uint32_t GnuHash(const char* name) {
uint32_t h = 5381;
const uint8_t* ptr = reinterpret_cast<const uint8_t*>(name);
while (*ptr) {
h = h * 33 + *ptr++;
}
return h;
}
GnuHashTable::GnuHashTable()
: num_buckets_(0),
sym_offset_(0),
sym_count_(0),
bloom_word_mask_(0),
bloom_shift_(0),
bloom_filter_(NULL),
buckets_(NULL),
chain_(NULL) {}
void GnuHashTable::Init(uintptr_t dt_gnu_hash) {
SB_DLOG(INFO) << "GnuHashTable::Init 0x" << std::hex << dt_gnu_hash;
sym_count_ = 0;
const uint32_t* data = reinterpret_cast<const uint32_t*>(dt_gnu_hash);
num_buckets_ = data[0];
sym_offset_ = data[1];
SB_DLOG(INFO) << "GnuHashTable::Init num_buckets_=" << num_buckets_
<< " sym_offset_" << sym_offset_;
if (!num_buckets_)
return;
const uint32_t bloom_size = data[2];
SB_DLOG(INFO) << "GnuHashTable::Init bloom_size=" << bloom_size;
if ((bloom_size & (bloom_size - 1U)) != 0) // must be a power of 2
return;
bloom_word_mask_ = bloom_size - 1U;
bloom_shift_ = data[3];
SB_DLOG(INFO) << "GnuHashTable::Init bloom_word_mask_=" << bloom_word_mask_;
SB_DLOG(INFO) << "GnuHashTable::Init bloom_shift_=" << bloom_shift_;
bloom_filter_ = reinterpret_cast<const Addr*>(data + 4);
SB_DLOG(INFO) << "GnuHashTable::Init bloom_filter_=0x" << std::hex
<< bloom_filter_;
buckets_ = reinterpret_cast<const uint32_t*>(bloom_filter_ + bloom_size);
SB_DLOG(INFO) << "GnuHashTable::Init buckets_=0x" << std::hex << buckets_;
chain_ = buckets_ + num_buckets_;
// Compute number of dynamic symbols by parsing the table.
if (num_buckets_ > 0) {
// First find the maximum index in the buckets table.
uint32_t max_index = buckets_[0];
for (size_t n = 1; n < num_buckets_; ++n) {
uint32_t sym_index = buckets_[n];
if (sym_index > max_index)
max_index = sym_index;
}
// Now start to look at the chain_ table from (max_index - sym_offset_)
// until there is a value with LSB set to 1, indicating the end of the
// last chain.
while ((chain_[max_index - sym_offset_] & 1) == 0)
max_index++;
sym_count_ = (max_index - sym_offset_) + 1;
}
}
bool GnuHashTable::IsValid() const {
return sym_count_ > 0;
}
const Sym* GnuHashTable::LookupByName(const char* symbol_name,
const Sym* symbol_table,
const char* string_table) const {
SB_DLOG(INFO) << "GnuHashTable::LookupByName: " << symbol_name;
uint32_t hash = GnuHash(symbol_name);
SB_DLOG(INFO) << "GnuHashTable::LookupByName: hash=" << hash;
SB_DLOG(INFO) << "GnuHashTable::LookupByName: ELF_BITS=" << ELF_BITS;
// First, bloom filter test.
Addr word = bloom_filter_[(hash / ELF_BITS) & bloom_word_mask_];
SB_DLOG(INFO) << "GnuHashTable::LookupByName: word=" << word;
Addr mask = (Addr(1) << (hash % ELF_BITS)) |
(Addr(1) << ((hash >> bloom_shift_) % ELF_BITS));
SB_DLOG(INFO) << "GnuHashTable::LookupByName: mask=" << mask;
if ((word & mask) != mask)
return NULL;
uint32_t sym_index = buckets_[hash % num_buckets_];
if (sym_index < sym_offset_)
return NULL;
// TODO: add validations of the syn_index
while (true) {
const Sym* sym = symbol_table + sym_index;
const uint32_t sym_hash = chain_[sym_index - sym_offset_];
const char* sym_name = string_table + sym->st_name;
if ((sym_hash | 1) == (hash | 1) && !strcmp(sym_name, symbol_name)) {
return sym;
}
if (sym_hash & 1)
break;
sym_index++;
}
return NULL;
}
} // namespace elf_loader
} // namespace starboard