1//===- MipsGOT.cpp --------------------------------------------------------===//
2//
3//                     The MCLinker Project
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include <llvm/Support/Casting.h>
11#include <llvm/Support/ELF.h>
12
13#include <mcld/LD/ResolveInfo.h>
14#include <mcld/Support/MsgHandling.h>
15#include <mcld/Target/OutputRelocSection.h>
16
17#include "MipsGOT.h"
18#include "MipsRelocator.h"
19
20namespace {
21  const uint32_t Mips32ModulePtr = 1 << 31;
22  const uint64_t Mips64ModulePtr = 1ull << 63;
23  const size_t MipsGOT0Num = 2;
24  const size_t MipsGOTGpOffset = 0x7FF0;
25  const size_t MipsGOTSize = MipsGOTGpOffset + 0x7FFF;
26}
27
28using namespace mcld;
29
30//===----------------------------------------------------------------------===//
31// MipsGOT::GOTMultipart
32//===----------------------------------------------------------------------===//
33MipsGOT::GOTMultipart::GOTMultipart(size_t local, size_t global)
34  : m_LocalNum(local),
35    m_GlobalNum(global),
36    m_ConsumedLocal(0),
37    m_ConsumedGlobal(0),
38    m_pLastLocal(NULL),
39    m_pLastGlobal(NULL)
40{
41}
42
43bool MipsGOT::GOTMultipart::isConsumed() const
44{
45  return m_LocalNum == m_ConsumedLocal &&
46         m_GlobalNum == m_ConsumedGlobal;
47}
48
49void MipsGOT::GOTMultipart::consumeLocal()
50{
51  assert(m_ConsumedLocal < m_LocalNum &&
52         "Consumed too many local GOT entries");
53  ++m_ConsumedLocal;
54  m_pLastLocal = m_pLastLocal->getNextNode();
55}
56
57void MipsGOT::GOTMultipart::consumeGlobal()
58{
59  assert(m_ConsumedGlobal < m_GlobalNum &&
60         "Consumed too many global GOT entries");
61  ++m_ConsumedGlobal;
62  m_pLastGlobal = m_pLastGlobal->getNextNode();
63}
64
65//===----------------------------------------------------------------------===//
66// MipsGOT::LocalEntry
67//===----------------------------------------------------------------------===//
68MipsGOT::LocalEntry::LocalEntry(const ResolveInfo* pInfo,
69                                Relocation::DWord addend, bool isGot16)
70  : m_pInfo(pInfo),
71    m_Addend(addend),
72    m_IsGot16(isGot16)
73{
74}
75
76bool MipsGOT::LocalEntry::operator<(const LocalEntry &O) const
77{
78  if (m_pInfo != O.m_pInfo)
79    return m_pInfo < O.m_pInfo;
80
81  if (m_Addend != O.m_Addend)
82    return m_Addend < O.m_Addend;
83
84  return m_IsGot16 < O.m_IsGot16;
85}
86
87//===----------------------------------------------------------------------===//
88// MipsGOT
89//===----------------------------------------------------------------------===//
90MipsGOT::MipsGOT(LDSection& pSection)
91  : GOT(pSection),
92    m_pInput(NULL),
93    m_CurrentGOTPart(0)
94{
95}
96
97uint64_t MipsGOT::getGPDispAddress() const
98{
99  return addr() + MipsGOTGpOffset;
100}
101
102void MipsGOT::reserve(size_t pNum)
103{
104  for (size_t i = 0; i < pNum; i++)
105    createEntry(0, m_SectionData);
106}
107
108bool MipsGOT::hasGOT1() const
109{
110  return !m_MultipartList.empty();
111}
112
113bool MipsGOT::hasMultipleGOT() const
114{
115  return m_MultipartList.size() > 1;
116}
117
118void MipsGOT::finalizeScanning(OutputRelocSection& pRelDyn)
119{
120  for (MultipartListType::iterator it = m_MultipartList.begin();
121       it != m_MultipartList.end(); ++it) {
122    reserveHeader();
123    it->m_pLastLocal = &m_SectionData->back();
124    reserve(it->m_LocalNum);
125    it->m_pLastGlobal = &m_SectionData->back();
126    reserve(it->m_GlobalNum);
127
128    if (it == m_MultipartList.begin())
129      // Reserve entries in the second part of the primary GOT.
130      // These entries correspond to the global symbols in all
131      // non-primary GOTs.
132      reserve(getGlobalNum() - it->m_GlobalNum);
133    else {
134      // Reserve reldyn entries for R_MIPS_REL32 relocations
135      // for all global entries of secondary GOTs.
136      // FIXME: (simon) Do not count local entries for non-pic.
137      size_t count = it->m_GlobalNum + it->m_LocalNum;
138      for (size_t i = 0; i < count; ++i)
139        pRelDyn.reserveEntry();
140    }
141  }
142}
143
144bool MipsGOT::dynSymOrderCompare(const LDSymbol* pX, const LDSymbol* pY) const
145{
146  SymbolOrderMapType::const_iterator itX = m_SymbolOrderMap.find(pX);
147  SymbolOrderMapType::const_iterator itY = m_SymbolOrderMap.find(pY);
148
149  if (itX != m_SymbolOrderMap.end() && itY != m_SymbolOrderMap.end())
150    return itX->second < itY->second;
151
152  return itX == m_SymbolOrderMap.end() && itY != m_SymbolOrderMap.end();
153}
154
155void MipsGOT::initGOTList()
156{
157  m_SymbolOrderMap.clear();
158
159  m_MultipartList.clear();
160  m_MultipartList.push_back(GOTMultipart());
161
162  m_MultipartList.back().m_Inputs.insert(m_pInput);
163
164  m_MergedGlobalSymbols.clear();
165  m_InputGlobalSymbols.clear();
166  m_MergedLocalSymbols.clear();
167  m_InputLocalSymbols.clear();
168}
169
170void MipsGOT::changeInput()
171{
172  m_MultipartList.back().m_Inputs.insert(m_pInput);
173
174  for (LocalSymbolSetType::iterator it = m_InputLocalSymbols.begin(),
175                                    end = m_InputLocalSymbols.end();
176       it != end; ++it)
177    m_MergedLocalSymbols.insert(*it);
178
179  m_InputLocalSymbols.clear();
180
181  for (SymbolUniqueMapType::iterator it = m_InputGlobalSymbols.begin(),
182                                     end = m_InputGlobalSymbols.end();
183       it != end; ++it)
184    m_MergedGlobalSymbols.insert(it->first);
185
186  m_InputGlobalSymbols.clear();
187}
188
189bool MipsGOT::isGOTFull() const
190{
191  uint64_t gotCount = MipsGOT0Num +
192                      m_MultipartList.back().m_LocalNum +
193                      m_MultipartList.back().m_GlobalNum;
194
195  gotCount += 1;
196
197  return gotCount * getEntrySize() > MipsGOTSize;
198}
199
200void MipsGOT::split()
201{
202  m_MergedLocalSymbols.clear();
203  m_MergedGlobalSymbols.clear();
204
205  size_t uniqueCount = 0;
206  for (SymbolUniqueMapType::const_iterator it = m_InputGlobalSymbols.begin(),
207                                           end = m_InputGlobalSymbols.end();
208       it != end; ++it) {
209    if (it->second)
210      ++uniqueCount;
211  }
212
213  m_MultipartList.back().m_LocalNum -= m_InputLocalSymbols.size();
214  m_MultipartList.back().m_GlobalNum -= uniqueCount;
215  m_MultipartList.back().m_Inputs.erase(m_pInput);
216
217  m_MultipartList.push_back(GOTMultipart(m_InputLocalSymbols.size(),
218                                         m_InputGlobalSymbols.size()));
219  m_MultipartList.back().m_Inputs.insert(m_pInput);
220}
221
222void MipsGOT::initializeScan(const Input& pInput)
223{
224  if (m_pInput == NULL) {
225    m_pInput = &pInput;
226    initGOTList();
227  }
228  else {
229    m_pInput = &pInput;
230    changeInput();
231  }
232}
233
234void MipsGOT::finalizeScan(const Input& pInput)
235{
236}
237
238bool MipsGOT::reserveLocalEntry(ResolveInfo& pInfo, int reloc,
239                                Relocation::DWord pAddend)
240{
241  LocalEntry entry(&pInfo, pAddend, reloc == llvm::ELF::R_MIPS_GOT16);
242
243  if (m_InputLocalSymbols.count(entry))
244    // Do nothing, if we have seen this symbol
245    // in the current input already.
246    return false;
247
248  if (m_MergedLocalSymbols.count(entry)) {
249    // We have seen this symbol in previous inputs.
250    // Remember that it exists in the current input too.
251    m_InputLocalSymbols.insert(entry);
252    return false;
253  }
254
255  if (isGOTFull())
256    split();
257
258  m_InputLocalSymbols.insert(entry);
259
260  ++m_MultipartList.back().m_LocalNum;
261  return true;
262}
263
264bool MipsGOT::reserveGlobalEntry(ResolveInfo& pInfo)
265{
266  if (m_InputGlobalSymbols.count(&pInfo))
267    return false;
268
269  if (m_MergedGlobalSymbols.count(&pInfo)) {
270    m_InputGlobalSymbols[&pInfo] = false;
271    return false;
272  }
273
274  if (isGOTFull())
275    split();
276
277  m_InputGlobalSymbols[&pInfo] = true;
278  ++m_MultipartList.back().m_GlobalNum;
279
280  if (!(pInfo.reserved() & MipsRelocator::ReserveGot)) {
281    m_SymbolOrderMap[pInfo.outSymbol()] = m_SymbolOrderMap.size();
282    pInfo.setReserved(pInfo.reserved() | MipsRelocator::ReserveGot);
283  }
284
285  return true;
286}
287
288bool MipsGOT::isPrimaryGOTConsumed()
289{
290  return m_CurrentGOTPart > 0;
291}
292
293Fragment* MipsGOT::consumeLocal()
294{
295  assert(m_CurrentGOTPart < m_MultipartList.size() && "GOT number is out of range!");
296
297  if (m_MultipartList[m_CurrentGOTPart].isConsumed())
298    ++m_CurrentGOTPart;
299
300  m_MultipartList[m_CurrentGOTPart].consumeLocal();
301
302  return m_MultipartList[m_CurrentGOTPart].m_pLastLocal;
303}
304
305Fragment* MipsGOT::consumeGlobal()
306{
307  assert(m_CurrentGOTPart < m_MultipartList.size() && "GOT number is out of range!");
308
309  if (m_MultipartList[m_CurrentGOTPart].isConsumed())
310    ++m_CurrentGOTPart;
311
312  m_MultipartList[m_CurrentGOTPart].consumeGlobal();
313
314  return m_MultipartList[m_CurrentGOTPart].m_pLastGlobal;
315}
316
317uint64_t MipsGOT::getGPAddr(const Input& pInput) const
318{
319  uint64_t gotSize = 0;
320  for (MultipartListType::const_iterator it = m_MultipartList.begin();
321                                         it != m_MultipartList.end(); ++it) {
322    if (it->m_Inputs.count(&pInput))
323      break;
324
325    gotSize += (MipsGOT0Num + it->m_LocalNum + it->m_GlobalNum);
326    if (it == m_MultipartList.begin())
327      gotSize += getGlobalNum() - it->m_GlobalNum;
328  }
329
330  return addr() + gotSize * getEntrySize() + MipsGOTGpOffset;
331}
332
333uint64_t MipsGOT::getGPRelOffset(const Input& pInput,
334                                 const Fragment& pEntry) const
335{
336  return addr() + pEntry.getOffset() - getGPAddr(pInput);
337}
338
339void MipsGOT::recordGlobalEntry(const ResolveInfo* pInfo, Fragment* pEntry)
340{
341  GotEntryKey key;
342  key.m_GOTPage = m_CurrentGOTPart;
343  key.m_pInfo = pInfo;
344  key.m_Addend = 0;
345  m_GotGlobalEntriesMap[key] = pEntry;
346}
347
348Fragment* MipsGOT::lookupGlobalEntry(const ResolveInfo* pInfo)
349{
350  GotEntryKey key;
351  key.m_GOTPage= m_CurrentGOTPart;
352  key.m_pInfo = pInfo;
353  key.m_Addend = 0;
354  GotEntryMapType::iterator it = m_GotGlobalEntriesMap.find(key);
355
356  if (it == m_GotGlobalEntriesMap.end())
357    return NULL;
358
359  return it->second;
360}
361
362void MipsGOT::recordLocalEntry(const ResolveInfo* pInfo,
363                               Relocation::DWord pAddend,
364                               Fragment* pEntry)
365{
366  GotEntryKey key;
367  key.m_GOTPage = m_CurrentGOTPart;
368  key.m_pInfo = pInfo;
369  key.m_Addend = pAddend;
370  m_GotLocalEntriesMap[key] = pEntry;
371}
372
373Fragment* MipsGOT::lookupLocalEntry(const ResolveInfo* pInfo,
374                                    Relocation::DWord pAddend)
375{
376  GotEntryKey key;
377  key.m_GOTPage= m_CurrentGOTPart;
378  key.m_pInfo = pInfo;
379  key.m_Addend = pAddend;
380  GotEntryMapType::iterator it = m_GotLocalEntriesMap.find(key);
381
382  if (it == m_GotLocalEntriesMap.end())
383    return NULL;
384
385  return it->second;
386}
387
388size_t MipsGOT::getLocalNum() const
389{
390  assert(!m_MultipartList.empty() && "GOT is empty!");
391  return m_MultipartList[0].m_LocalNum + MipsGOT0Num;
392}
393
394size_t MipsGOT::getGlobalNum() const
395{
396  return m_SymbolOrderMap.size();
397}
398
399//===----------------------------------------------------------------------===//
400// Mips32GOT
401//===----------------------------------------------------------------------===//
402Mips32GOT::Mips32GOT(LDSection& pSection)
403  : MipsGOT(pSection)
404{}
405
406void Mips32GOT::setEntryValue(Fragment* entry, uint64_t pValue)
407{
408  llvm::cast<Mips32GOTEntry>(entry)->setValue(pValue);
409}
410
411uint64_t Mips32GOT::emit(MemoryRegion& pRegion)
412{
413  uint32_t* buffer = reinterpret_cast<uint32_t*>(pRegion.begin());
414
415  uint64_t result = 0;
416  for (iterator it = begin(), ie = end(); it != ie; ++it, ++buffer) {
417    Mips32GOTEntry* got = &(llvm::cast<Mips32GOTEntry>((*it)));
418    *buffer = static_cast<uint32_t>(got->getValue());
419    result += got->size();
420  }
421  return result;
422}
423
424Fragment* Mips32GOT::createEntry(uint64_t pValue, SectionData* pParent)
425{
426  return new Mips32GOTEntry(pValue, pParent);
427}
428
429size_t Mips32GOT::getEntrySize() const
430{
431  return Mips32GOTEntry::EntrySize;
432}
433
434void Mips32GOT::reserveHeader()
435{
436  createEntry(0, m_SectionData);
437  createEntry(Mips32ModulePtr, m_SectionData);
438}
439
440//===----------------------------------------------------------------------===//
441// Mips64GOT
442//===----------------------------------------------------------------------===//
443Mips64GOT::Mips64GOT(LDSection& pSection)
444  : MipsGOT(pSection)
445{}
446
447void Mips64GOT::setEntryValue(Fragment* entry, uint64_t pValue)
448{
449  llvm::cast<Mips64GOTEntry>(entry)->setValue(pValue);
450}
451
452uint64_t Mips64GOT::emit(MemoryRegion& pRegion)
453{
454  uint64_t* buffer = reinterpret_cast<uint64_t*>(pRegion.begin());
455
456  uint64_t result = 0;
457  for (iterator it = begin(), ie = end(); it != ie; ++it, ++buffer) {
458    Mips64GOTEntry* got = &(llvm::cast<Mips64GOTEntry>((*it)));
459    *buffer = static_cast<uint64_t>(got->getValue());
460    result += got->size();
461  }
462  return result;
463}
464
465Fragment* Mips64GOT::createEntry(uint64_t pValue, SectionData* pParent)
466{
467  return new Mips64GOTEntry(pValue, pParent);
468}
469
470size_t Mips64GOT::getEntrySize() const
471{
472  return Mips64GOTEntry::EntrySize;
473}
474
475void Mips64GOT::reserveHeader()
476{
477  createEntry(0, m_SectionData);
478  createEntry(Mips64ModulePtr, m_SectionData);
479}
480