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 "mcld/LD/ResolveInfo.h"
11 #include "mcld/Support/MsgHandling.h"
12 #include "mcld/Target/OutputRelocSection.h"
13 
14 #include "MipsGOT.h"
15 #include "MipsRelocator.h"
16 
17 #include <llvm/Support/Casting.h>
18 #include <llvm/Support/ELF.h>
19 
20 namespace {
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 
28 namespace mcld {
29 
30 //===----------------------------------------------------------------------===//
31 // MipsGOT::GOTMultipart
32 //===----------------------------------------------------------------------===//
GOTMultipart(size_t local,size_t global)33 MipsGOT::GOTMultipart::GOTMultipart(size_t local, size_t global)
34     : m_LocalNum(local),
35       m_GlobalNum(global),
36       m_TLSNum(0),
37       m_TLSDynNum(0),
38       m_ConsumedLocal(0),
39       m_ConsumedGlobal(0),
40       m_ConsumedTLS(0),
41       m_pLastLocal(NULL),
42       m_pLastGlobal(NULL),
43       m_pLastTLS(NULL) {
44 }
45 
isConsumed() const46 bool MipsGOT::GOTMultipart::isConsumed() const {
47   return m_LocalNum == m_ConsumedLocal && m_GlobalNum == m_ConsumedGlobal &&
48          m_TLSNum == m_ConsumedTLS;
49 }
50 
consumeLocal()51 void MipsGOT::GOTMultipart::consumeLocal() {
52   assert(m_ConsumedLocal < m_LocalNum && "Consumed too many local GOT entries");
53   ++m_ConsumedLocal;
54   m_pLastLocal = m_pLastLocal->getNextNode();
55 }
56 
consumeGlobal()57 void MipsGOT::GOTMultipart::consumeGlobal() {
58   assert(m_ConsumedGlobal < m_GlobalNum &&
59          "Consumed too many global GOT entries");
60   ++m_ConsumedGlobal;
61   m_pLastGlobal = m_pLastGlobal->getNextNode();
62 }
63 
consumeTLS(Relocation::Type pType)64 void MipsGOT::GOTMultipart::consumeTLS(Relocation::Type pType) {
65   assert(m_ConsumedTLS < m_TLSNum &&
66          "Consumed too many TLS GOT entries");
67   m_ConsumedTLS += pType == llvm::ELF::R_MIPS_TLS_GOTTPREL ? 1 : 2;
68   m_pLastTLS = m_pLastTLS->getNextNode();
69 }
70 
71 //===----------------------------------------------------------------------===//
72 // MipsGOT::LocalEntry
73 //===----------------------------------------------------------------------===//
LocalEntry(const ResolveInfo * pInfo,Relocation::DWord addend,bool isGot16)74 MipsGOT::LocalEntry::LocalEntry(const ResolveInfo* pInfo,
75                                 Relocation::DWord addend,
76                                 bool isGot16)
77     : m_pInfo(pInfo), m_Addend(addend), m_IsGot16(isGot16) {
78 }
79 
operator <(const LocalEntry & O) const80 bool MipsGOT::LocalEntry::operator<(const LocalEntry& O) const {
81   if (m_pInfo != O.m_pInfo)
82     return m_pInfo < O.m_pInfo;
83 
84   if (m_Addend != O.m_Addend)
85     return m_Addend < O.m_Addend;
86 
87   return m_IsGot16 < O.m_IsGot16;
88 }
89 
90 //===----------------------------------------------------------------------===//
91 // MipsGOT
92 //===----------------------------------------------------------------------===//
MipsGOT(LDSection & pSection)93 MipsGOT::MipsGOT(LDSection& pSection)
94     : GOT(pSection),
95       m_pInput(NULL),
96       m_HasTLSLdmSymbol(false),
97       m_CurrentGOTPart(0),
98       m_GotTLSLdmEntry(nullptr) {
99 }
100 
getGPDispAddress() const101 uint64_t MipsGOT::getGPDispAddress() const {
102   return addr() + MipsGOTGpOffset;
103 }
104 
reserve(size_t pNum)105 void MipsGOT::reserve(size_t pNum) {
106   for (size_t i = 0; i < pNum; ++i)
107     createEntry(0, m_SectionData);
108 }
109 
hasGOT1() const110 bool MipsGOT::hasGOT1() const {
111   return !m_MultipartList.empty();
112 }
113 
hasMultipleGOT() const114 bool MipsGOT::hasMultipleGOT() const {
115   return m_MultipartList.size() > 1;
116 }
117 
finalizeScanning(OutputRelocSection & pRelDyn)118 void MipsGOT::finalizeScanning(OutputRelocSection& pRelDyn) {
119   for (MultipartListType::iterator it = m_MultipartList.begin();
120        it != m_MultipartList.end();
121        ++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     it->m_pLastTLS = &m_SectionData->back();
128     reserve(it->m_TLSNum);
129 
130     if (it == m_MultipartList.begin()) {
131       // Reserve entries in the second part of the primary GOT.
132       // These entries correspond to the global symbols in all
133       // non-primary GOTs.
134       reserve(getGlobalNum() - it->m_GlobalNum);
135     } else {
136       // Reserve reldyn entries for R_MIPS_REL32 relocations
137       // for all global entries of secondary GOTs.
138       // FIXME: (simon) Do not count local entries for non-pic.
139       size_t count = it->m_GlobalNum + it->m_LocalNum;
140       for (size_t i = 0; i < count; ++i)
141         pRelDyn.reserveEntry();
142     }
143 
144     for (size_t i = 0; i < it->m_TLSDynNum; ++i)
145       pRelDyn.reserveEntry();
146   }
147 }
148 
dynSymOrderCompare(const LDSymbol * pX,const LDSymbol * pY) const149 bool MipsGOT::dynSymOrderCompare(const LDSymbol* pX, const LDSymbol* pY) const {
150   SymbolOrderMapType::const_iterator itX = m_SymbolOrderMap.find(pX);
151   SymbolOrderMapType::const_iterator itY = m_SymbolOrderMap.find(pY);
152 
153   if (itX != m_SymbolOrderMap.end() && itY != m_SymbolOrderMap.end())
154     return itX->second < itY->second;
155 
156   return itX == m_SymbolOrderMap.end() && itY != m_SymbolOrderMap.end();
157 }
158 
initGOTList()159 void MipsGOT::initGOTList() {
160   m_SymbolOrderMap.clear();
161 
162   m_MultipartList.clear();
163   m_MultipartList.push_back(GOTMultipart());
164 
165   m_MultipartList.back().m_Inputs.insert(m_pInput);
166 
167   m_MergedGlobalSymbols.clear();
168   m_InputGlobalSymbols.clear();
169   m_MergedLocalSymbols.clear();
170   m_InputLocalSymbols.clear();
171   m_InputTLSGdSymbols.clear();
172   m_HasTLSLdmSymbol = false;
173 }
174 
changeInput()175 void MipsGOT::changeInput() {
176   m_MultipartList.back().m_Inputs.insert(m_pInput);
177 
178   for (LocalSymbolSetType::iterator it = m_InputLocalSymbols.begin(),
179                                     end = m_InputLocalSymbols.end();
180        it != end;
181        ++it)
182     m_MergedLocalSymbols.insert(*it);
183 
184   m_InputLocalSymbols.clear();
185 
186   for (SymbolUniqueMapType::iterator it = m_InputGlobalSymbols.begin(),
187                                      end = m_InputGlobalSymbols.end();
188        it != end;
189        ++it)
190     m_MergedGlobalSymbols.insert(it->first);
191 
192   m_InputGlobalSymbols.clear();
193 }
194 
isGOTFull() const195 bool MipsGOT::isGOTFull() const {
196   uint64_t gotCount = MipsGOT0Num + m_MultipartList.back().m_LocalNum +
197                       m_MultipartList.back().m_GlobalNum;
198 
199   gotCount += 1;
200 
201   return gotCount * getEntrySize() > MipsGOTSize;
202 }
203 
split()204 void MipsGOT::split() {
205   m_MergedLocalSymbols.clear();
206   m_MergedGlobalSymbols.clear();
207 
208   size_t uniqueCount = 0;
209   for (SymbolUniqueMapType::const_iterator it = m_InputGlobalSymbols.begin(),
210                                            end = m_InputGlobalSymbols.end();
211        it != end;
212        ++it) {
213     if (it->second)
214       ++uniqueCount;
215   }
216 
217   m_MultipartList.back().m_LocalNum -= m_InputLocalSymbols.size();
218   m_MultipartList.back().m_GlobalNum -= uniqueCount;
219   m_MultipartList.back().m_Inputs.erase(m_pInput);
220 
221   m_MultipartList.push_back(
222       GOTMultipart(m_InputLocalSymbols.size(), m_InputGlobalSymbols.size()));
223   m_MultipartList.back().m_Inputs.insert(m_pInput);
224 }
225 
initializeScan(const Input & pInput)226 void MipsGOT::initializeScan(const Input& pInput) {
227   if (m_pInput == NULL) {
228     m_pInput = &pInput;
229     initGOTList();
230   } else {
231     m_pInput = &pInput;
232     changeInput();
233   }
234 }
235 
finalizeScan(const Input & pInput)236 void MipsGOT::finalizeScan(const Input& pInput) {
237 }
238 
reserveLocalEntry(ResolveInfo & pInfo,int reloc,Relocation::DWord pAddend)239 bool MipsGOT::reserveLocalEntry(ResolveInfo& pInfo,
240                                 int reloc,
241                                 Relocation::DWord pAddend) {
242   LocalEntry entry(&pInfo, pAddend, reloc == llvm::ELF::R_MIPS_GOT16);
243 
244   if (m_InputLocalSymbols.count(entry))
245     // Do nothing, if we have seen this symbol
246     // in the current input already.
247     return false;
248 
249   if (m_MergedLocalSymbols.count(entry)) {
250     // We have seen this symbol in previous inputs.
251     // Remember that it exists in the current input too.
252     m_InputLocalSymbols.insert(entry);
253     return false;
254   }
255 
256   if (isGOTFull())
257     split();
258 
259   m_InputLocalSymbols.insert(entry);
260 
261   ++m_MultipartList.back().m_LocalNum;
262   return true;
263 }
264 
reserveGlobalEntry(ResolveInfo & pInfo)265 bool MipsGOT::reserveGlobalEntry(ResolveInfo& pInfo) {
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 
reserveTLSGdEntry(ResolveInfo & pInfo)288 bool MipsGOT::reserveTLSGdEntry(ResolveInfo& pInfo) {
289   if (m_InputTLSGdSymbols.count(&pInfo))
290     return false;
291 
292   m_InputTLSGdSymbols.insert(&pInfo);
293   m_MultipartList.back().m_TLSNum += 2;
294   m_MultipartList.back().m_TLSDynNum += 2;
295 
296   return true;
297 }
298 
reserveTLSLdmEntry()299 bool MipsGOT::reserveTLSLdmEntry() {
300   if (m_HasTLSLdmSymbol)
301     return false;
302 
303   m_HasTLSLdmSymbol = true;
304   m_MultipartList.back().m_TLSNum += 2;
305   m_MultipartList.back().m_TLSDynNum += 1;
306 
307   return true;
308 }
309 
reserveTLSGotEntry(ResolveInfo & pInfo)310 bool MipsGOT::reserveTLSGotEntry(ResolveInfo& pInfo) {
311   if (m_InputTLSGotSymbols.count(&pInfo))
312     return false;
313 
314   m_InputTLSGotSymbols.insert(&pInfo);
315   m_MultipartList.back().m_TLSNum += 1;
316   m_MultipartList.back().m_TLSDynNum += 1;
317 
318   return true;
319 }
320 
isPrimaryGOTConsumed()321 bool MipsGOT::isPrimaryGOTConsumed() {
322   return m_CurrentGOTPart > 0;
323 }
324 
consumeLocal()325 Fragment* MipsGOT::consumeLocal() {
326   assert(m_CurrentGOTPart < m_MultipartList.size() &&
327          "GOT number is out of range!");
328 
329   if (m_MultipartList[m_CurrentGOTPart].isConsumed())
330     ++m_CurrentGOTPart;
331 
332   m_MultipartList[m_CurrentGOTPart].consumeLocal();
333 
334   return m_MultipartList[m_CurrentGOTPart].m_pLastLocal;
335 }
336 
consumeGlobal()337 Fragment* MipsGOT::consumeGlobal() {
338   assert(m_CurrentGOTPart < m_MultipartList.size() &&
339          "GOT number is out of range!");
340 
341   if (m_MultipartList[m_CurrentGOTPart].isConsumed())
342     ++m_CurrentGOTPart;
343 
344   m_MultipartList[m_CurrentGOTPart].consumeGlobal();
345 
346   return m_MultipartList[m_CurrentGOTPart].m_pLastGlobal;
347 }
348 
consumeTLS(Relocation::Type pType)349 Fragment* MipsGOT::consumeTLS(Relocation::Type pType) {
350   assert(m_CurrentGOTPart < m_MultipartList.size() &&
351          "GOT number is out of range!");
352 
353   if (m_MultipartList[m_CurrentGOTPart].isConsumed())
354     ++m_CurrentGOTPart;
355 
356   m_MultipartList[m_CurrentGOTPart].consumeTLS(pType);
357 
358   return m_MultipartList[m_CurrentGOTPart].m_pLastTLS;
359 }
360 
getGPAddr(const Input & pInput) const361 uint64_t MipsGOT::getGPAddr(const Input& pInput) const {
362   uint64_t gotSize = 0;
363   for (MultipartListType::const_iterator it = m_MultipartList.begin(),
364                                          ie = m_MultipartList.end();
365        it != ie;
366        ++it) {
367     if (it->m_Inputs.count(&pInput))
368       break;
369 
370     gotSize += (MipsGOT0Num + it->m_LocalNum + it->m_GlobalNum);
371     if (it == m_MultipartList.begin())
372       gotSize += getGlobalNum() - it->m_GlobalNum;
373   }
374 
375   return addr() + gotSize * getEntrySize() + MipsGOTGpOffset;
376 }
377 
getGPRelOffset(const Input & pInput,const Fragment & pEntry) const378 uint64_t MipsGOT::getGPRelOffset(const Input& pInput,
379                                  const Fragment& pEntry) const {
380   return addr() + pEntry.getOffset() - getGPAddr(pInput);
381 }
382 
recordGlobalEntry(const ResolveInfo * pInfo,Fragment * pEntry)383 void MipsGOT::recordGlobalEntry(const ResolveInfo* pInfo, Fragment* pEntry) {
384   GotEntryKey key;
385   key.m_GOTPage = m_CurrentGOTPart;
386   key.m_pInfo = pInfo;
387   key.m_Addend = 0;
388   m_GotGlobalEntriesMap[key] = pEntry;
389 }
390 
lookupGlobalEntry(const ResolveInfo * pInfo)391 Fragment* MipsGOT::lookupGlobalEntry(const ResolveInfo* pInfo) {
392   GotEntryKey key;
393   key.m_GOTPage = m_CurrentGOTPart;
394   key.m_pInfo = pInfo;
395   key.m_Addend = 0;
396   GotEntryMapType::iterator it = m_GotGlobalEntriesMap.find(key);
397 
398   if (it == m_GotGlobalEntriesMap.end())
399     return NULL;
400 
401   return it->second;
402 }
403 
recordTLSEntry(const ResolveInfo * pInfo,Fragment * pEntry,Relocation::Type pType)404 void MipsGOT::recordTLSEntry(const ResolveInfo* pInfo, Fragment* pEntry,
405                              Relocation::Type pType) {
406   if (pType == llvm::ELF::R_MIPS_TLS_LDM) {
407     m_GotTLSLdmEntry = pEntry;
408   } else if (pType == llvm::ELF::R_MIPS_TLS_GD) {
409     GotEntryKey key;
410     key.m_GOTPage = m_CurrentGOTPart;
411     key.m_pInfo = pInfo;
412     key.m_Addend = 0;
413     m_GotTLSGdEntriesMap[key] = pEntry;
414   } else if (pType == llvm::ELF::R_MIPS_TLS_GOTTPREL) {
415     GotEntryKey key;
416     key.m_GOTPage = m_CurrentGOTPart;
417     key.m_pInfo = pInfo;
418     key.m_Addend = 0;
419     m_GotTLSGotEntriesMap[key] = pEntry;
420   } else {
421     llvm_unreachable("Unexpected relocation");
422   }
423 }
424 
lookupTLSEntry(const ResolveInfo * pInfo,Relocation::Type pType)425 Fragment* MipsGOT::lookupTLSEntry(const ResolveInfo* pInfo,
426                                   Relocation::Type pType) {
427   if (pType == llvm::ELF::R_MIPS_TLS_LDM)
428     return m_GotTLSLdmEntry;
429   if (pType == llvm::ELF::R_MIPS_TLS_GD) {
430     GotEntryKey key;
431     key.m_GOTPage = m_CurrentGOTPart;
432     key.m_pInfo = pInfo;
433     key.m_Addend = 0;
434     GotEntryMapType::iterator it = m_GotTLSGdEntriesMap.find(key);
435     return it == m_GotTLSGdEntriesMap.end() ? nullptr : it->second;
436   }
437   if (pType == llvm::ELF::R_MIPS_TLS_GOTTPREL) {
438     GotEntryKey key;
439     key.m_GOTPage = m_CurrentGOTPart;
440     key.m_pInfo = pInfo;
441     key.m_Addend = 0;
442     GotEntryMapType::iterator it = m_GotTLSGotEntriesMap.find(key);
443     return it == m_GotTLSGotEntriesMap.end() ? nullptr : it->second;
444   }
445   llvm_unreachable("Unexpected relocation");
446 }
447 
recordLocalEntry(const ResolveInfo * pInfo,Relocation::DWord pAddend,Fragment * pEntry)448 void MipsGOT::recordLocalEntry(const ResolveInfo* pInfo,
449                                Relocation::DWord pAddend,
450                                Fragment* pEntry) {
451   GotEntryKey key;
452   key.m_GOTPage = m_CurrentGOTPart;
453   key.m_pInfo = pInfo;
454   key.m_Addend = pAddend;
455   m_GotLocalEntriesMap[key] = pEntry;
456 }
457 
lookupLocalEntry(const ResolveInfo * pInfo,Relocation::DWord pAddend)458 Fragment* MipsGOT::lookupLocalEntry(const ResolveInfo* pInfo,
459                                     Relocation::DWord pAddend) {
460   GotEntryKey key;
461   key.m_GOTPage = m_CurrentGOTPart;
462   key.m_pInfo = pInfo;
463   key.m_Addend = pAddend;
464   GotEntryMapType::iterator it = m_GotLocalEntriesMap.find(key);
465 
466   if (it == m_GotLocalEntriesMap.end())
467     return NULL;
468 
469   return it->second;
470 }
471 
getLocalNum() const472 size_t MipsGOT::getLocalNum() const {
473   assert(!m_MultipartList.empty() && "GOT is empty!");
474   return m_MultipartList[0].m_LocalNum + MipsGOT0Num;
475 }
476 
getGlobalNum() const477 size_t MipsGOT::getGlobalNum() const {
478   return m_SymbolOrderMap.size();
479 }
480 
481 //===----------------------------------------------------------------------===//
482 // Mips32GOT
483 //===----------------------------------------------------------------------===//
Mips32GOT(LDSection & pSection)484 Mips32GOT::Mips32GOT(LDSection& pSection) : MipsGOT(pSection) {
485 }
486 
setEntryValue(Fragment * entry,uint64_t pValue)487 void Mips32GOT::setEntryValue(Fragment* entry, uint64_t pValue) {
488   llvm::cast<Mips32GOTEntry>(entry)->setValue(pValue);
489 }
490 
emit(MemoryRegion & pRegion)491 uint64_t Mips32GOT::emit(MemoryRegion& pRegion) {
492   uint32_t* buffer = reinterpret_cast<uint32_t*>(pRegion.begin());
493 
494   uint64_t result = 0;
495   for (iterator it = begin(), ie = end(); it != ie; ++it, ++buffer) {
496     Mips32GOTEntry* got = &(llvm::cast<Mips32GOTEntry>((*it)));
497     *buffer = static_cast<uint32_t>(got->getValue());
498     result += got->size();
499   }
500   return result;
501 }
502 
createEntry(uint64_t pValue,SectionData * pParent)503 Fragment* Mips32GOT::createEntry(uint64_t pValue, SectionData* pParent) {
504   return new Mips32GOTEntry(pValue, pParent);
505 }
506 
getEntrySize() const507 size_t Mips32GOT::getEntrySize() const {
508   return Mips32GOTEntry::EntrySize;
509 }
510 
reserveHeader()511 void Mips32GOT::reserveHeader() {
512   createEntry(0, m_SectionData);
513   createEntry(Mips32ModulePtr, m_SectionData);
514 }
515 
516 //===----------------------------------------------------------------------===//
517 // Mips64GOT
518 //===----------------------------------------------------------------------===//
Mips64GOT(LDSection & pSection)519 Mips64GOT::Mips64GOT(LDSection& pSection) : MipsGOT(pSection) {
520 }
521 
setEntryValue(Fragment * entry,uint64_t pValue)522 void Mips64GOT::setEntryValue(Fragment* entry, uint64_t pValue) {
523   llvm::cast<Mips64GOTEntry>(entry)->setValue(pValue);
524 }
525 
emit(MemoryRegion & pRegion)526 uint64_t Mips64GOT::emit(MemoryRegion& pRegion) {
527   uint64_t* buffer = reinterpret_cast<uint64_t*>(pRegion.begin());
528 
529   uint64_t result = 0;
530   for (iterator it = begin(), ie = end(); it != ie; ++it, ++buffer) {
531     Mips64GOTEntry* got = &(llvm::cast<Mips64GOTEntry>((*it)));
532     *buffer = static_cast<uint64_t>(got->getValue());
533     result += got->size();
534   }
535   return result;
536 }
537 
createEntry(uint64_t pValue,SectionData * pParent)538 Fragment* Mips64GOT::createEntry(uint64_t pValue, SectionData* pParent) {
539   return new Mips64GOTEntry(pValue, pParent);
540 }
541 
getEntrySize() const542 size_t Mips64GOT::getEntrySize() const {
543   return Mips64GOTEntry::EntrySize;
544 }
545 
reserveHeader()546 void Mips64GOT::reserveHeader() {
547   createEntry(0, m_SectionData);
548   createEntry(Mips64ModulePtr, m_SectionData);
549 }
550 
551 }  // namespace mcld
552