//===- MipsGOT.cpp --------------------------------------------------------===//
//
//                     The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#include <llvm/Support/Casting.h>
#include <llvm/Support/ELF.h>

#include <mcld/LD/ResolveInfo.h>
#include <mcld/Support/MsgHandling.h>
#include <mcld/Target/OutputRelocSection.h>

#include "MipsGOT.h"
#include "MipsRelocator.h"

namespace {
  const uint32_t Mips32ModulePtr = 1 << 31;
  const uint64_t Mips64ModulePtr = 1ull << 63;
  const size_t MipsGOT0Num = 2;
  const size_t MipsGOTGpOffset = 0x7FF0;
  const size_t MipsGOTSize = MipsGOTGpOffset + 0x7FFF;
}

using namespace mcld;

//===----------------------------------------------------------------------===//
// MipsGOT::GOTMultipart
//===----------------------------------------------------------------------===//
MipsGOT::GOTMultipart::GOTMultipart(size_t local, size_t global)
  : m_LocalNum(local),
    m_GlobalNum(global),
    m_ConsumedLocal(0),
    m_ConsumedGlobal(0),
    m_pLastLocal(NULL),
    m_pLastGlobal(NULL)
{
}

bool MipsGOT::GOTMultipart::isConsumed() const
{
  return m_LocalNum == m_ConsumedLocal &&
         m_GlobalNum == m_ConsumedGlobal;
}

void MipsGOT::GOTMultipart::consumeLocal()
{
  assert(m_ConsumedLocal < m_LocalNum &&
         "Consumed too many local GOT entries");
  ++m_ConsumedLocal;
  m_pLastLocal = m_pLastLocal->getNextNode();
}

void MipsGOT::GOTMultipart::consumeGlobal()
{
  assert(m_ConsumedGlobal < m_GlobalNum &&
         "Consumed too many global GOT entries");
  ++m_ConsumedGlobal;
  m_pLastGlobal = m_pLastGlobal->getNextNode();
}

//===----------------------------------------------------------------------===//
// MipsGOT::LocalEntry
//===----------------------------------------------------------------------===//
MipsGOT::LocalEntry::LocalEntry(const ResolveInfo* pInfo,
                                Relocation::DWord addend, bool isGot16)
  : m_pInfo(pInfo),
    m_Addend(addend),
    m_IsGot16(isGot16)
{
}

bool MipsGOT::LocalEntry::operator<(const LocalEntry &O) const
{
  if (m_pInfo != O.m_pInfo)
    return m_pInfo < O.m_pInfo;

  if (m_Addend != O.m_Addend)
    return m_Addend < O.m_Addend;

  return m_IsGot16 < O.m_IsGot16;
}

//===----------------------------------------------------------------------===//
// MipsGOT
//===----------------------------------------------------------------------===//
MipsGOT::MipsGOT(LDSection& pSection)
  : GOT(pSection),
    m_pInput(NULL),
    m_CurrentGOTPart(0)
{
}

uint64_t MipsGOT::getGPDispAddress() const
{
  return addr() + MipsGOTGpOffset;
}

void MipsGOT::reserve(size_t pNum)
{
  for (size_t i = 0; i < pNum; i++)
    createEntry(0, m_SectionData);
}

bool MipsGOT::hasGOT1() const
{
  return !m_MultipartList.empty();
}

bool MipsGOT::hasMultipleGOT() const
{
  return m_MultipartList.size() > 1;
}

void MipsGOT::finalizeScanning(OutputRelocSection& pRelDyn)
{
  for (MultipartListType::iterator it = m_MultipartList.begin();
       it != m_MultipartList.end(); ++it) {
    reserveHeader();
    it->m_pLastLocal = &m_SectionData->back();
    reserve(it->m_LocalNum);
    it->m_pLastGlobal = &m_SectionData->back();
    reserve(it->m_GlobalNum);

    if (it == m_MultipartList.begin())
      // Reserve entries in the second part of the primary GOT.
      // These entries correspond to the global symbols in all
      // non-primary GOTs.
      reserve(getGlobalNum() - it->m_GlobalNum);
    else {
      // Reserve reldyn entries for R_MIPS_REL32 relocations
      // for all global entries of secondary GOTs.
      // FIXME: (simon) Do not count local entries for non-pic.
      size_t count = it->m_GlobalNum + it->m_LocalNum;
      for (size_t i = 0; i < count; ++i)
        pRelDyn.reserveEntry();
    }
  }
}

bool MipsGOT::dynSymOrderCompare(const LDSymbol* pX, const LDSymbol* pY) const
{
  SymbolOrderMapType::const_iterator itX = m_SymbolOrderMap.find(pX);
  SymbolOrderMapType::const_iterator itY = m_SymbolOrderMap.find(pY);

  if (itX != m_SymbolOrderMap.end() && itY != m_SymbolOrderMap.end())
    return itX->second < itY->second;

  return itX == m_SymbolOrderMap.end() && itY != m_SymbolOrderMap.end();
}

void MipsGOT::initGOTList()
{
  m_SymbolOrderMap.clear();

  m_MultipartList.clear();
  m_MultipartList.push_back(GOTMultipart());

  m_MultipartList.back().m_Inputs.insert(m_pInput);

  m_MergedGlobalSymbols.clear();
  m_InputGlobalSymbols.clear();
  m_MergedLocalSymbols.clear();
  m_InputLocalSymbols.clear();
}

void MipsGOT::changeInput()
{
  m_MultipartList.back().m_Inputs.insert(m_pInput);

  for (LocalSymbolSetType::iterator it = m_InputLocalSymbols.begin(),
                                    end = m_InputLocalSymbols.end();
       it != end; ++it)
    m_MergedLocalSymbols.insert(*it);

  m_InputLocalSymbols.clear();

  for (SymbolUniqueMapType::iterator it = m_InputGlobalSymbols.begin(),
                                     end = m_InputGlobalSymbols.end();
       it != end; ++it)
    m_MergedGlobalSymbols.insert(it->first);

  m_InputGlobalSymbols.clear();
}

bool MipsGOT::isGOTFull() const
{
  uint64_t gotCount = MipsGOT0Num +
                      m_MultipartList.back().m_LocalNum +
                      m_MultipartList.back().m_GlobalNum;

  gotCount += 1;

  return gotCount * getEntrySize() > MipsGOTSize;
}

void MipsGOT::split()
{
  m_MergedLocalSymbols.clear();
  m_MergedGlobalSymbols.clear();

  size_t uniqueCount = 0;
  for (SymbolUniqueMapType::const_iterator it = m_InputGlobalSymbols.begin(),
                                           end = m_InputGlobalSymbols.end();
       it != end; ++it) {
    if (it->second)
      ++uniqueCount;
  }

  m_MultipartList.back().m_LocalNum -= m_InputLocalSymbols.size();
  m_MultipartList.back().m_GlobalNum -= uniqueCount;
  m_MultipartList.back().m_Inputs.erase(m_pInput);

  m_MultipartList.push_back(GOTMultipart(m_InputLocalSymbols.size(),
                                         m_InputGlobalSymbols.size()));
  m_MultipartList.back().m_Inputs.insert(m_pInput);
}

void MipsGOT::initializeScan(const Input& pInput)
{
  if (m_pInput == NULL) {
    m_pInput = &pInput;
    initGOTList();
  }
  else {
    m_pInput = &pInput;
    changeInput();
  }
}

void MipsGOT::finalizeScan(const Input& pInput)
{
}

bool MipsGOT::reserveLocalEntry(ResolveInfo& pInfo, int reloc,
                                Relocation::DWord pAddend)
{
  LocalEntry entry(&pInfo, pAddend, reloc == llvm::ELF::R_MIPS_GOT16);

  if (m_InputLocalSymbols.count(entry))
    // Do nothing, if we have seen this symbol
    // in the current input already.
    return false;

  if (m_MergedLocalSymbols.count(entry)) {
    // We have seen this symbol in previous inputs.
    // Remember that it exists in the current input too.
    m_InputLocalSymbols.insert(entry);
    return false;
  }

  if (isGOTFull())
    split();

  m_InputLocalSymbols.insert(entry);

  ++m_MultipartList.back().m_LocalNum;
  return true;
}

bool MipsGOT::reserveGlobalEntry(ResolveInfo& pInfo)
{
  if (m_InputGlobalSymbols.count(&pInfo))
    return false;

  if (m_MergedGlobalSymbols.count(&pInfo)) {
    m_InputGlobalSymbols[&pInfo] = false;
    return false;
  }

  if (isGOTFull())
    split();

  m_InputGlobalSymbols[&pInfo] = true;
  ++m_MultipartList.back().m_GlobalNum;

  if (!(pInfo.reserved() & MipsRelocator::ReserveGot)) {
    m_SymbolOrderMap[pInfo.outSymbol()] = m_SymbolOrderMap.size();
    pInfo.setReserved(pInfo.reserved() | MipsRelocator::ReserveGot);
  }

  return true;
}

bool MipsGOT::isPrimaryGOTConsumed()
{
  return m_CurrentGOTPart > 0;
}

Fragment* MipsGOT::consumeLocal()
{
  assert(m_CurrentGOTPart < m_MultipartList.size() && "GOT number is out of range!");

  if (m_MultipartList[m_CurrentGOTPart].isConsumed())
    ++m_CurrentGOTPart;

  m_MultipartList[m_CurrentGOTPart].consumeLocal();

  return m_MultipartList[m_CurrentGOTPart].m_pLastLocal;
}

Fragment* MipsGOT::consumeGlobal()
{
  assert(m_CurrentGOTPart < m_MultipartList.size() && "GOT number is out of range!");

  if (m_MultipartList[m_CurrentGOTPart].isConsumed())
    ++m_CurrentGOTPart;

  m_MultipartList[m_CurrentGOTPart].consumeGlobal();

  return m_MultipartList[m_CurrentGOTPart].m_pLastGlobal;
}

uint64_t MipsGOT::getGPAddr(const Input& pInput) const
{
  uint64_t gotSize = 0;
  for (MultipartListType::const_iterator it = m_MultipartList.begin();
                                         it != m_MultipartList.end(); ++it) {
    if (it->m_Inputs.count(&pInput))
      break;

    gotSize += (MipsGOT0Num + it->m_LocalNum + it->m_GlobalNum);
    if (it == m_MultipartList.begin())
      gotSize += getGlobalNum() - it->m_GlobalNum;
  }

  return addr() + gotSize * getEntrySize() + MipsGOTGpOffset;
}

uint64_t MipsGOT::getGPRelOffset(const Input& pInput,
                                 const Fragment& pEntry) const
{
  return addr() + pEntry.getOffset() - getGPAddr(pInput);
}

void MipsGOT::recordGlobalEntry(const ResolveInfo* pInfo, Fragment* pEntry)
{
  GotEntryKey key;
  key.m_GOTPage = m_CurrentGOTPart;
  key.m_pInfo = pInfo;
  key.m_Addend = 0;
  m_GotGlobalEntriesMap[key] = pEntry;
}

Fragment* MipsGOT::lookupGlobalEntry(const ResolveInfo* pInfo)
{
  GotEntryKey key;
  key.m_GOTPage= m_CurrentGOTPart;
  key.m_pInfo = pInfo;
  key.m_Addend = 0;
  GotEntryMapType::iterator it = m_GotGlobalEntriesMap.find(key);

  if (it == m_GotGlobalEntriesMap.end())
    return NULL;

  return it->second;
}

void MipsGOT::recordLocalEntry(const ResolveInfo* pInfo,
                               Relocation::DWord pAddend,
                               Fragment* pEntry)
{
  GotEntryKey key;
  key.m_GOTPage = m_CurrentGOTPart;
  key.m_pInfo = pInfo;
  key.m_Addend = pAddend;
  m_GotLocalEntriesMap[key] = pEntry;
}

Fragment* MipsGOT::lookupLocalEntry(const ResolveInfo* pInfo,
                                    Relocation::DWord pAddend)
{
  GotEntryKey key;
  key.m_GOTPage= m_CurrentGOTPart;
  key.m_pInfo = pInfo;
  key.m_Addend = pAddend;
  GotEntryMapType::iterator it = m_GotLocalEntriesMap.find(key);

  if (it == m_GotLocalEntriesMap.end())
    return NULL;

  return it->second;
}

size_t MipsGOT::getLocalNum() const
{
  assert(!m_MultipartList.empty() && "GOT is empty!");
  return m_MultipartList[0].m_LocalNum + MipsGOT0Num;
}

size_t MipsGOT::getGlobalNum() const
{
  return m_SymbolOrderMap.size();
}

//===----------------------------------------------------------------------===//
// Mips32GOT
//===----------------------------------------------------------------------===//
Mips32GOT::Mips32GOT(LDSection& pSection)
  : MipsGOT(pSection)
{}

void Mips32GOT::setEntryValue(Fragment* entry, uint64_t pValue)
{
  llvm::cast<Mips32GOTEntry>(entry)->setValue(pValue);
}

uint64_t Mips32GOT::emit(MemoryRegion& pRegion)
{
  uint32_t* buffer = reinterpret_cast<uint32_t*>(pRegion.begin());

  uint64_t result = 0;
  for (iterator it = begin(), ie = end(); it != ie; ++it, ++buffer) {
    Mips32GOTEntry* got = &(llvm::cast<Mips32GOTEntry>((*it)));
    *buffer = static_cast<uint32_t>(got->getValue());
    result += got->size();
  }
  return result;
}

Fragment* Mips32GOT::createEntry(uint64_t pValue, SectionData* pParent)
{
  return new Mips32GOTEntry(pValue, pParent);
}

size_t Mips32GOT::getEntrySize() const
{
  return Mips32GOTEntry::EntrySize;
}

void Mips32GOT::reserveHeader()
{
  createEntry(0, m_SectionData);
  createEntry(Mips32ModulePtr, m_SectionData);
}

//===----------------------------------------------------------------------===//
// Mips64GOT
//===----------------------------------------------------------------------===//
Mips64GOT::Mips64GOT(LDSection& pSection)
  : MipsGOT(pSection)
{}

void Mips64GOT::setEntryValue(Fragment* entry, uint64_t pValue)
{
  llvm::cast<Mips64GOTEntry>(entry)->setValue(pValue);
}

uint64_t Mips64GOT::emit(MemoryRegion& pRegion)
{
  uint64_t* buffer = reinterpret_cast<uint64_t*>(pRegion.begin());

  uint64_t result = 0;
  for (iterator it = begin(), ie = end(); it != ie; ++it, ++buffer) {
    Mips64GOTEntry* got = &(llvm::cast<Mips64GOTEntry>((*it)));
    *buffer = static_cast<uint64_t>(got->getValue());
    result += got->size();
  }
  return result;
}

Fragment* Mips64GOT::createEntry(uint64_t pValue, SectionData* pParent)
{
  return new Mips64GOTEntry(pValue, pParent);
}

size_t Mips64GOT::getEntrySize() const
{
  return Mips64GOTEntry::EntrySize;
}

void Mips64GOT::reserveHeader()
{
  createEntry(0, m_SectionData);
  createEntry(Mips64ModulePtr, m_SectionData);
}