SymbolTable.cc

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#include "pedigree/kernel/LockGuard.h"
#include "pedigree/kernel/linker/SymbolTable.h"
#include "pedigree/kernel/utilities/Iterator.h"
 
#define RAII_LOCK ConstexprLockGuard<Mutex, THREADS> guard(m_Lock)
 
SymbolTable::SymbolTable(Elf* pElf)
    : m_LocalSymbols(),
      m_GlobalSymbols(),
      m_WeakSymbols(),
      m_pOriginatingElf(pElf),
      m_bPreallocated(false) {}
 
SymbolTable::~SymbolTable() {}
 
void SymbolTable::copyTable(Elf* pNewElf, const SymbolTable& newSymtab) {
  RAII_LOCK;
 
  // Safe to do this, all members are SharedPointers and will be copy
  // constructed by these operations.
  m_LocalSymbols = newSymtab.m_LocalSymbols;
  m_GlobalSymbols = newSymtab.m_GlobalSymbols;
  m_WeakSymbols = newSymtab.m_WeakSymbols;
}
 
void SymbolTable::insert(const String& name, Binding binding, Elf* pParent, uintptr_t value) {
  RAII_LOCK;
 
  doInsert(name, binding, pParent, value);
}
 
void SymbolTable::insertMultiple(SymbolTable* pOther, const String& name, Binding binding,
                                 Elf* pParent, uintptr_t value) {
  RAII_LOCK;
  ConstexprLockGuard<Mutex, THREADS> guard2(pOther->m_Lock);
 
  SharedPointer<Symbol> ptr = doInsert(name, binding, pParent, value);
  if (pOther)
    pOther->insertShared(name, ptr);
}
 
void SymbolTable::preallocate(size_t numGlobal, size_t numWeak, Elf* localElf, size_t numLocal) {
  RAII_LOCK;
 
  auto tree = getOrInsertTree(localElf);
  tree->reserve(numLocal);
 
  tree = getOrInsertTree(localElf, Global);
  tree->reserve(numGlobal);
 
  tree = getOrInsertTree(localElf, Weak);
  tree->reserve(numWeak);
 
  m_bPreallocated = true;
}
 
void SymbolTable::preallocateAdditional(size_t numGlobal, size_t numWeak, Elf* localElf,
                                        size_t numLocal) {
  RAII_LOCK;
 
  auto tree = getOrInsertTree(localElf, Global);
  tree->reserve(tree->count() + numGlobal);
 
  tree = getOrInsertTree(localElf, Weak);
  tree->reserve(tree->count() + numWeak);
 
  tree = getOrInsertTree(localElf);
  tree->reserve(tree->count() + numLocal);
 
  m_bPreallocated = true;
}
 
bool SymbolTable::hasPreallocated() const {
  RAII_LOCK;
  return m_bPreallocated;
}
 
SharedPointer<SymbolTable::Symbol> SymbolTable::doInsert(const String& name, Binding binding,
                                                         Elf* pParent, uintptr_t value) {
  Symbol* pSymbol = new Symbol(pParent, binding, value);
  SharedPointer<Symbol> newSymbol(pSymbol);
 
  insertShared(name, newSymbol);
  return newSymbol;
}
 
void SymbolTable::insertShared(const String& name, SharedPointer<SymbolTable::Symbol>& symbol) {
  auto tree = getOrInsertTree(symbol->getParent(), symbol->getBinding());
  tree->insert(name, symbol);
}
 
void SymbolTable::eraseByElf(Elf* pParent) {
  RAII_LOCK;
 
  // Will wipe out recursively by destroying the SharedPointers within.
  m_LocalSymbols.remove(pParent);
  m_GlobalSymbols.remove(pParent);
  m_WeakSymbols.remove(pParent);
}
 
uintptr_t SymbolTable::lookup(const HashedStringView& name, Elf* pElf, Policy policy,
                              Binding* pBinding) {
  RAII_LOCK;
 
  // safe empty SharedPointer we can use for lookupRef()'s failed result
  static SharedPointer<symbolTree_t> failedLookup;
 
  uintptr_t lookupResult = 0;
 
  // Local to the ELF file itself.
  if (policy != NotOriginatingElf) {
    const SharedPointer<symbolTree_t>& symbolTree = m_LocalSymbols.lookupRef(pElf, failedLookup);
    if (symbolTree) {
      symbolTree_t::LookupResult result = symbolTree->lookup(name);
      if (result.hasValue()) {
        lookupResult = result.value()->getValue();
      }
    }
  }
 
  // Global lookup across all ELFs that expose global symbols.
  if (!lookupResult) {
    for (parentedSymbolTree_t::Iterator it = m_GlobalSymbols.begin(); it != m_GlobalSymbols.end();
         ++it) {
      symbolTree_t::LookupResult result = it.value(failedLookup)->lookup(name);
      if (result.hasValue()) {
        lookupResult = result.value()->getValue();
        break;
      }
    }
  }
 
  // Finally we try and find a usable weak symbol.
  if (!lookupResult) {
    for (parentedSymbolTree_t::Iterator it = m_WeakSymbols.begin(); it != m_WeakSymbols.end();
         ++it) {
      symbolTree_t::LookupResult result = it.value(failedLookup)->lookup(name);
      if (result.hasValue()) {
        lookupResult = result.value()->getValue();
        break;
      }
    }
  }
 
  // NOTICE("SymbolTable::lookup(" << name << ", " << pElf->getName() << ")
  // ==> " << Hex << lookupResult);
 
  return lookupResult;
}
 
uintptr_t SymbolTable::lookupOwned(const HashedStringView& name, Elf* owner) {
  RAII_LOCK;
  static SharedPointer<symbolTree_t> missing;
  const parentedSymbolTree_t* tables[] = {&m_GlobalSymbols, &m_WeakSymbols};
  for (const auto* table : tables) {
    const auto& symbols = table->lookupRef(owner, missing);
    if (symbols) {
      auto found = symbols->lookup(name);
      if (found.hasValue()) {
        return found.value()->getValue();
      }
    }
  }
  return 0;
}
 
SymbolTable::symbolTree_t* SymbolTable::getOrInsertTree(Elf* p, Binding table) {
  // safe empty SharedPointer we can use for lookupRef()'s failed result
  static SharedPointer<symbolTree_t> v;
 
  Tree<Elf*, SharedPointer<symbolTree_t>>* tree = nullptr;
  switch (table) {
    case Local:
      tree = &m_LocalSymbols;
      break;
    case Global:
      tree = &m_GlobalSymbols;
      break;
    default:
      tree = &m_WeakSymbols;
      break;
  }
 
  auto symbolTree = tree->lookupRef(p, v);
  if (symbolTree) {
    return symbolTree.get();
  }
 
  auto newTree = SharedPointer<symbolTree_t>::allocate();
  auto result = newTree.get();
  tree->insert(p, pedigree_std::move(newTree));
  return result;
}