1 //===- OutputSections.cpp -------------------------------------------------===//
2 //
3 //                             The LLVM Linker
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 "OutputSections.h"
11 #include "Config.h"
12 #include "EhFrame.h"
13 #include "GdbIndex.h"
14 #include "LinkerScript.h"
15 #include "Memory.h"
16 #include "Strings.h"
17 #include "SymbolListFile.h"
18 #include "SymbolTable.h"
19 #include "SyntheticSections.h"
20 #include "Target.h"
21 #include "lld/Core/Parallel.h"
22 #include "llvm/Support/Dwarf.h"
23 #include "llvm/Support/MD5.h"
24 #include "llvm/Support/MathExtras.h"
25 #include "llvm/Support/SHA1.h"
26 
27 using namespace llvm;
28 using namespace llvm::dwarf;
29 using namespace llvm::object;
30 using namespace llvm::support::endian;
31 using namespace llvm::ELF;
32 
33 using namespace lld;
34 using namespace lld::elf;
35 
36 OutputSectionBase::OutputSectionBase(StringRef Name, uint32_t Type,
37                                      uint64_t Flags)
38     : Name(Name) {
39   this->Type = Type;
40   this->Flags = Flags;
41   this->Addralign = 1;
42 }
43 
44 uint32_t OutputSectionBase::getPhdrFlags() const {
45   uint32_t Ret = PF_R;
46   if (Flags & SHF_WRITE)
47     Ret |= PF_W;
48   if (Flags & SHF_EXECINSTR)
49     Ret |= PF_X;
50   return Ret;
51 }
52 
53 template <class ELFT>
54 void OutputSectionBase::writeHeaderTo(typename ELFT::Shdr *Shdr) {
55   Shdr->sh_entsize = Entsize;
56   Shdr->sh_addralign = Addralign;
57   Shdr->sh_type = Type;
58   Shdr->sh_offset = Offset;
59   Shdr->sh_flags = Flags;
60   Shdr->sh_info = Info;
61   Shdr->sh_link = Link;
62   Shdr->sh_addr = Addr;
63   Shdr->sh_size = Size;
64   Shdr->sh_name = ShName;
65 }
66 
67 template <class ELFT>
68 GdbIndexSection<ELFT>::GdbIndexSection()
69     : OutputSectionBase(".gdb_index", SHT_PROGBITS, 0) {}
70 
71 template <class ELFT> void GdbIndexSection<ELFT>::parseDebugSections() {
72   std::vector<InputSection<ELFT> *> &IS =
73       static_cast<OutputSection<ELFT> *>(Out<ELFT>::DebugInfo)->Sections;
74 
75   for (InputSection<ELFT> *I : IS)
76     readDwarf(I);
77 }
78 
79 template <class ELFT>
80 void GdbIndexSection<ELFT>::readDwarf(InputSection<ELFT> *I) {
81   std::vector<std::pair<uintX_t, uintX_t>> CuList = readCuList(I);
82   CompilationUnits.insert(CompilationUnits.end(), CuList.begin(), CuList.end());
83 }
84 
85 template <class ELFT> void GdbIndexSection<ELFT>::finalize() {
86   parseDebugSections();
87 
88   // GdbIndex header consist from version fields
89   // and 5 more fields with different kinds of offsets.
90   CuTypesOffset = CuListOffset + CompilationUnits.size() * CompilationUnitSize;
91   this->Size = CuTypesOffset;
92 }
93 
94 template <class ELFT> void GdbIndexSection<ELFT>::writeTo(uint8_t *Buf) {
95   write32le(Buf, 7);                  // Write Version
96   write32le(Buf + 4, CuListOffset);   // CU list offset
97   write32le(Buf + 8, CuTypesOffset);  // Types CU list offset
98   write32le(Buf + 12, CuTypesOffset); // Address area offset
99   write32le(Buf + 16, CuTypesOffset); // Symbol table offset
100   write32le(Buf + 20, CuTypesOffset); // Constant pool offset
101   Buf += 24;
102 
103   // Write the CU list.
104   for (std::pair<uintX_t, uintX_t> CU : CompilationUnits) {
105     write64le(Buf, CU.first);
106     write64le(Buf + 8, CU.second);
107     Buf += 16;
108   }
109 }
110 
111 template <class ELFT>
112 PltSection<ELFT>::PltSection()
113     : OutputSectionBase(".plt", SHT_PROGBITS, SHF_ALLOC | SHF_EXECINSTR) {
114   this->Addralign = 16;
115 }
116 
117 template <class ELFT> void PltSection<ELFT>::writeTo(uint8_t *Buf) {
118   // At beginning of PLT, we have code to call the dynamic linker
119   // to resolve dynsyms at runtime. Write such code.
120   Target->writePltHeader(Buf);
121   size_t Off = Target->PltHeaderSize;
122 
123   for (auto &I : Entries) {
124     const SymbolBody *B = I.first;
125     unsigned RelOff = I.second;
126     uint64_t Got = B->getGotPltVA<ELFT>();
127     uint64_t Plt = this->Addr + Off;
128     Target->writePlt(Buf + Off, Got, Plt, B->PltIndex, RelOff);
129     Off += Target->PltEntrySize;
130   }
131 }
132 
133 template <class ELFT> void PltSection<ELFT>::addEntry(SymbolBody &Sym) {
134   Sym.PltIndex = Entries.size();
135   unsigned RelOff = Out<ELFT>::RelaPlt->getRelocOffset();
136   Entries.push_back(std::make_pair(&Sym, RelOff));
137 }
138 
139 template <class ELFT> void PltSection<ELFT>::finalize() {
140   this->Size = Target->PltHeaderSize + Entries.size() * Target->PltEntrySize;
141 }
142 
143 template <class ELFT>
144 RelocationSection<ELFT>::RelocationSection(StringRef Name, bool Sort)
145     : OutputSectionBase(Name, Config->Rela ? SHT_RELA : SHT_REL, SHF_ALLOC),
146       Sort(Sort) {
147   this->Entsize = Config->Rela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
148   this->Addralign = sizeof(uintX_t);
149 }
150 
151 template <class ELFT>
152 void RelocationSection<ELFT>::addReloc(const DynamicReloc<ELFT> &Reloc) {
153   if (Reloc.Type == Target->RelativeRel)
154     ++NumRelativeRelocs;
155   Relocs.push_back(Reloc);
156 }
157 
158 template <class ELFT, class RelTy>
159 static bool compRelocations(const RelTy &A, const RelTy &B) {
160   bool AIsRel = A.getType(Config->Mips64EL) == Target->RelativeRel;
161   bool BIsRel = B.getType(Config->Mips64EL) == Target->RelativeRel;
162   if (AIsRel != BIsRel)
163     return AIsRel;
164 
165   return A.getSymbol(Config->Mips64EL) < B.getSymbol(Config->Mips64EL);
166 }
167 
168 template <class ELFT> void RelocationSection<ELFT>::writeTo(uint8_t *Buf) {
169   uint8_t *BufBegin = Buf;
170   for (const DynamicReloc<ELFT> &Rel : Relocs) {
171     auto *P = reinterpret_cast<Elf_Rela *>(Buf);
172     Buf += Config->Rela ? sizeof(Elf_Rela) : sizeof(Elf_Rel);
173 
174     if (Config->Rela)
175       P->r_addend = Rel.getAddend();
176     P->r_offset = Rel.getOffset();
177     if (Config->EMachine == EM_MIPS && Rel.getInputSec() == In<ELFT>::Got)
178       // Dynamic relocation against MIPS GOT section make deal TLS entries
179       // allocated in the end of the GOT. We need to adjust the offset to take
180       // in account 'local' and 'global' GOT entries.
181       P->r_offset += In<ELFT>::Got->getMipsTlsOffset();
182     P->setSymbolAndType(Rel.getSymIndex(), Rel.Type, Config->Mips64EL);
183   }
184 
185   if (Sort) {
186     if (Config->Rela)
187       std::stable_sort((Elf_Rela *)BufBegin,
188                        (Elf_Rela *)BufBegin + Relocs.size(),
189                        compRelocations<ELFT, Elf_Rela>);
190     else
191       std::stable_sort((Elf_Rel *)BufBegin, (Elf_Rel *)BufBegin + Relocs.size(),
192                        compRelocations<ELFT, Elf_Rel>);
193   }
194 }
195 
196 template <class ELFT> unsigned RelocationSection<ELFT>::getRelocOffset() {
197   return this->Entsize * Relocs.size();
198 }
199 
200 template <class ELFT> void RelocationSection<ELFT>::finalize() {
201   this->Link = Out<ELFT>::DynSymTab ? Out<ELFT>::DynSymTab->SectionIndex
202                                     : Out<ELFT>::SymTab->SectionIndex;
203   this->Size = Relocs.size() * this->Entsize;
204 }
205 
206 template <class ELFT>
207 HashTableSection<ELFT>::HashTableSection()
208     : OutputSectionBase(".hash", SHT_HASH, SHF_ALLOC) {
209   this->Entsize = sizeof(Elf_Word);
210   this->Addralign = sizeof(Elf_Word);
211 }
212 
213 template <class ELFT> void HashTableSection<ELFT>::finalize() {
214   this->Link = Out<ELFT>::DynSymTab->SectionIndex;
215 
216   unsigned NumEntries = 2;                             // nbucket and nchain.
217   NumEntries += Out<ELFT>::DynSymTab->getNumSymbols(); // The chain entries.
218 
219   // Create as many buckets as there are symbols.
220   // FIXME: This is simplistic. We can try to optimize it, but implementing
221   // support for SHT_GNU_HASH is probably even more profitable.
222   NumEntries += Out<ELFT>::DynSymTab->getNumSymbols();
223   this->Size = NumEntries * sizeof(Elf_Word);
224 }
225 
226 template <class ELFT> void HashTableSection<ELFT>::writeTo(uint8_t *Buf) {
227   unsigned NumSymbols = Out<ELFT>::DynSymTab->getNumSymbols();
228   auto *P = reinterpret_cast<Elf_Word *>(Buf);
229   *P++ = NumSymbols; // nbucket
230   *P++ = NumSymbols; // nchain
231 
232   Elf_Word *Buckets = P;
233   Elf_Word *Chains = P + NumSymbols;
234 
235   for (const SymbolTableEntry &S : Out<ELFT>::DynSymTab->getSymbols()) {
236     SymbolBody *Body = S.Symbol;
237     StringRef Name = Body->getName();
238     unsigned I = Body->DynsymIndex;
239     uint32_t Hash = hashSysV(Name) % NumSymbols;
240     Chains[I] = Buckets[Hash];
241     Buckets[Hash] = I;
242   }
243 }
244 
245 static uint32_t hashGnu(StringRef Name) {
246   uint32_t H = 5381;
247   for (uint8_t C : Name)
248     H = (H << 5) + H + C;
249   return H;
250 }
251 
252 template <class ELFT>
253 GnuHashTableSection<ELFT>::GnuHashTableSection()
254     : OutputSectionBase(".gnu.hash", SHT_GNU_HASH, SHF_ALLOC) {
255   this->Entsize = ELFT::Is64Bits ? 0 : 4;
256   this->Addralign = sizeof(uintX_t);
257 }
258 
259 template <class ELFT>
260 unsigned GnuHashTableSection<ELFT>::calcNBuckets(unsigned NumHashed) {
261   if (!NumHashed)
262     return 0;
263 
264   // These values are prime numbers which are not greater than 2^(N-1) + 1.
265   // In result, for any particular NumHashed we return a prime number
266   // which is not greater than NumHashed.
267   static const unsigned Primes[] = {
268       1,   1,    3,    3,    7,    13,    31,    61,    127,   251,
269       509, 1021, 2039, 4093, 8191, 16381, 32749, 65521, 131071};
270 
271   return Primes[std::min<unsigned>(Log2_32_Ceil(NumHashed),
272                                    array_lengthof(Primes) - 1)];
273 }
274 
275 // Bloom filter estimation: at least 8 bits for each hashed symbol.
276 // GNU Hash table requirement: it should be a power of 2,
277 //   the minimum value is 1, even for an empty table.
278 // Expected results for a 32-bit target:
279 //   calcMaskWords(0..4)   = 1
280 //   calcMaskWords(5..8)   = 2
281 //   calcMaskWords(9..16)  = 4
282 // For a 64-bit target:
283 //   calcMaskWords(0..8)   = 1
284 //   calcMaskWords(9..16)  = 2
285 //   calcMaskWords(17..32) = 4
286 template <class ELFT>
287 unsigned GnuHashTableSection<ELFT>::calcMaskWords(unsigned NumHashed) {
288   if (!NumHashed)
289     return 1;
290   return NextPowerOf2((NumHashed - 1) / sizeof(Elf_Off));
291 }
292 
293 template <class ELFT> void GnuHashTableSection<ELFT>::finalize() {
294   unsigned NumHashed = Symbols.size();
295   NBuckets = calcNBuckets(NumHashed);
296   MaskWords = calcMaskWords(NumHashed);
297   // Second hash shift estimation: just predefined values.
298   Shift2 = ELFT::Is64Bits ? 6 : 5;
299 
300   this->Link = Out<ELFT>::DynSymTab->SectionIndex;
301   this->Size = sizeof(Elf_Word) * 4            // Header
302                + sizeof(Elf_Off) * MaskWords   // Bloom Filter
303                + sizeof(Elf_Word) * NBuckets   // Hash Buckets
304                + sizeof(Elf_Word) * NumHashed; // Hash Values
305 }
306 
307 template <class ELFT> void GnuHashTableSection<ELFT>::writeTo(uint8_t *Buf) {
308   writeHeader(Buf);
309   if (Symbols.empty())
310     return;
311   writeBloomFilter(Buf);
312   writeHashTable(Buf);
313 }
314 
315 template <class ELFT>
316 void GnuHashTableSection<ELFT>::writeHeader(uint8_t *&Buf) {
317   auto *P = reinterpret_cast<Elf_Word *>(Buf);
318   *P++ = NBuckets;
319   *P++ = Out<ELFT>::DynSymTab->getNumSymbols() - Symbols.size();
320   *P++ = MaskWords;
321   *P++ = Shift2;
322   Buf = reinterpret_cast<uint8_t *>(P);
323 }
324 
325 template <class ELFT>
326 void GnuHashTableSection<ELFT>::writeBloomFilter(uint8_t *&Buf) {
327   unsigned C = sizeof(Elf_Off) * 8;
328 
329   auto *Masks = reinterpret_cast<Elf_Off *>(Buf);
330   for (const SymbolData &Sym : Symbols) {
331     size_t Pos = (Sym.Hash / C) & (MaskWords - 1);
332     uintX_t V = (uintX_t(1) << (Sym.Hash % C)) |
333                 (uintX_t(1) << ((Sym.Hash >> Shift2) % C));
334     Masks[Pos] |= V;
335   }
336   Buf += sizeof(Elf_Off) * MaskWords;
337 }
338 
339 template <class ELFT>
340 void GnuHashTableSection<ELFT>::writeHashTable(uint8_t *Buf) {
341   Elf_Word *Buckets = reinterpret_cast<Elf_Word *>(Buf);
342   Elf_Word *Values = Buckets + NBuckets;
343 
344   int PrevBucket = -1;
345   int I = 0;
346   for (const SymbolData &Sym : Symbols) {
347     int Bucket = Sym.Hash % NBuckets;
348     assert(PrevBucket <= Bucket);
349     if (Bucket != PrevBucket) {
350       Buckets[Bucket] = Sym.Body->DynsymIndex;
351       PrevBucket = Bucket;
352       if (I > 0)
353         Values[I - 1] |= 1;
354     }
355     Values[I] = Sym.Hash & ~1;
356     ++I;
357   }
358   if (I > 0)
359     Values[I - 1] |= 1;
360 }
361 
362 // Add symbols to this symbol hash table. Note that this function
363 // destructively sort a given vector -- which is needed because
364 // GNU-style hash table places some sorting requirements.
365 template <class ELFT>
366 void GnuHashTableSection<ELFT>::addSymbols(std::vector<SymbolTableEntry> &V) {
367   // Ideally this will just be 'auto' but GCC 6.1 is not able
368   // to deduce it correctly.
369   std::vector<SymbolTableEntry>::iterator Mid =
370       std::stable_partition(V.begin(), V.end(), [](const SymbolTableEntry &S) {
371         return S.Symbol->isUndefined();
372       });
373   if (Mid == V.end())
374     return;
375   for (auto I = Mid, E = V.end(); I != E; ++I) {
376     SymbolBody *B = I->Symbol;
377     size_t StrOff = I->StrTabOffset;
378     Symbols.push_back({B, StrOff, hashGnu(B->getName())});
379   }
380 
381   unsigned NBuckets = calcNBuckets(Symbols.size());
382   std::stable_sort(Symbols.begin(), Symbols.end(),
383                    [&](const SymbolData &L, const SymbolData &R) {
384                      return L.Hash % NBuckets < R.Hash % NBuckets;
385                    });
386 
387   V.erase(Mid, V.end());
388   for (const SymbolData &Sym : Symbols)
389     V.push_back({Sym.Body, Sym.STName});
390 }
391 
392 // Returns the number of version definition entries. Because the first entry
393 // is for the version definition itself, it is the number of versioned symbols
394 // plus one. Note that we don't support multiple versions yet.
395 static unsigned getVerDefNum() { return Config->VersionDefinitions.size() + 1; }
396 
397 template <class ELFT>
398 DynamicSection<ELFT>::DynamicSection()
399     : OutputSectionBase(".dynamic", SHT_DYNAMIC, SHF_ALLOC | SHF_WRITE) {
400   this->Addralign = sizeof(uintX_t);
401   this->Entsize = ELFT::Is64Bits ? 16 : 8;
402 
403   // .dynamic section is not writable on MIPS.
404   // See "Special Section" in Chapter 4 in the following document:
405   // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
406   if (Config->EMachine == EM_MIPS)
407     this->Flags = SHF_ALLOC;
408 
409   addEntries();
410 }
411 
412 // There are some dynamic entries that don't depend on other sections.
413 // Such entries can be set early.
414 template <class ELFT> void DynamicSection<ELFT>::addEntries() {
415   // Add strings to .dynstr early so that .dynstr's size will be
416   // fixed early.
417   for (StringRef S : Config->AuxiliaryList)
418     Add({DT_AUXILIARY, In<ELFT>::DynStrTab->addString(S)});
419   if (!Config->RPath.empty())
420     Add({Config->EnableNewDtags ? DT_RUNPATH : DT_RPATH,
421          In<ELFT>::DynStrTab->addString(Config->RPath)});
422   for (SharedFile<ELFT> *F : Symtab<ELFT>::X->getSharedFiles())
423     if (F->isNeeded())
424       Add({DT_NEEDED, In<ELFT>::DynStrTab->addString(F->getSoName())});
425   if (!Config->SoName.empty())
426     Add({DT_SONAME, In<ELFT>::DynStrTab->addString(Config->SoName)});
427 
428   // Set DT_FLAGS and DT_FLAGS_1.
429   uint32_t DtFlags = 0;
430   uint32_t DtFlags1 = 0;
431   if (Config->Bsymbolic)
432     DtFlags |= DF_SYMBOLIC;
433   if (Config->ZNodelete)
434     DtFlags1 |= DF_1_NODELETE;
435   if (Config->ZNow) {
436     DtFlags |= DF_BIND_NOW;
437     DtFlags1 |= DF_1_NOW;
438   }
439   if (Config->ZOrigin) {
440     DtFlags |= DF_ORIGIN;
441     DtFlags1 |= DF_1_ORIGIN;
442   }
443 
444   if (DtFlags)
445     Add({DT_FLAGS, DtFlags});
446   if (DtFlags1)
447     Add({DT_FLAGS_1, DtFlags1});
448 
449   if (!Config->Entry.empty())
450     Add({DT_DEBUG, (uint64_t)0});
451 }
452 
453 // Add remaining entries to complete .dynamic contents.
454 template <class ELFT> void DynamicSection<ELFT>::finalize() {
455   if (this->Size)
456     return; // Already finalized.
457 
458   this->Link = In<ELFT>::DynStrTab->OutSec->SectionIndex;
459 
460   if (Out<ELFT>::RelaDyn->hasRelocs()) {
461     bool IsRela = Config->Rela;
462     Add({IsRela ? DT_RELA : DT_REL, Out<ELFT>::RelaDyn});
463     Add({IsRela ? DT_RELASZ : DT_RELSZ, Out<ELFT>::RelaDyn->Size});
464     Add({IsRela ? DT_RELAENT : DT_RELENT,
465          uintX_t(IsRela ? sizeof(Elf_Rela) : sizeof(Elf_Rel))});
466 
467     // MIPS dynamic loader does not support RELCOUNT tag.
468     // The problem is in the tight relation between dynamic
469     // relocations and GOT. So do not emit this tag on MIPS.
470     if (Config->EMachine != EM_MIPS) {
471       size_t NumRelativeRels = Out<ELFT>::RelaDyn->getRelativeRelocCount();
472       if (Config->ZCombreloc && NumRelativeRels)
473         Add({IsRela ? DT_RELACOUNT : DT_RELCOUNT, NumRelativeRels});
474     }
475   }
476   if (Out<ELFT>::RelaPlt && Out<ELFT>::RelaPlt->hasRelocs()) {
477     Add({DT_JMPREL, Out<ELFT>::RelaPlt});
478     Add({DT_PLTRELSZ, Out<ELFT>::RelaPlt->Size});
479     Add({Config->EMachine == EM_MIPS ? DT_MIPS_PLTGOT : DT_PLTGOT,
480          In<ELFT>::GotPlt});
481     Add({DT_PLTREL, uint64_t(Config->Rela ? DT_RELA : DT_REL)});
482   }
483 
484   Add({DT_SYMTAB, Out<ELFT>::DynSymTab});
485   Add({DT_SYMENT, sizeof(Elf_Sym)});
486   Add({DT_STRTAB, In<ELFT>::DynStrTab});
487   Add({DT_STRSZ, In<ELFT>::DynStrTab->getSize()});
488   if (Out<ELFT>::GnuHashTab)
489     Add({DT_GNU_HASH, Out<ELFT>::GnuHashTab});
490   if (Out<ELFT>::HashTab)
491     Add({DT_HASH, Out<ELFT>::HashTab});
492 
493   if (Out<ELFT>::PreinitArray) {
494     Add({DT_PREINIT_ARRAY, Out<ELFT>::PreinitArray});
495     Add({DT_PREINIT_ARRAYSZ, Out<ELFT>::PreinitArray, Entry::SecSize});
496   }
497   if (Out<ELFT>::InitArray) {
498     Add({DT_INIT_ARRAY, Out<ELFT>::InitArray});
499     Add({DT_INIT_ARRAYSZ, Out<ELFT>::InitArray, Entry::SecSize});
500   }
501   if (Out<ELFT>::FiniArray) {
502     Add({DT_FINI_ARRAY, Out<ELFT>::FiniArray});
503     Add({DT_FINI_ARRAYSZ, Out<ELFT>::FiniArray, Entry::SecSize});
504   }
505 
506   if (SymbolBody *B = Symtab<ELFT>::X->find(Config->Init))
507     Add({DT_INIT, B});
508   if (SymbolBody *B = Symtab<ELFT>::X->find(Config->Fini))
509     Add({DT_FINI, B});
510 
511   bool HasVerNeed = Out<ELFT>::VerNeed->getNeedNum() != 0;
512   if (HasVerNeed || Out<ELFT>::VerDef)
513     Add({DT_VERSYM, Out<ELFT>::VerSym});
514   if (Out<ELFT>::VerDef) {
515     Add({DT_VERDEF, Out<ELFT>::VerDef});
516     Add({DT_VERDEFNUM, getVerDefNum()});
517   }
518   if (HasVerNeed) {
519     Add({DT_VERNEED, Out<ELFT>::VerNeed});
520     Add({DT_VERNEEDNUM, Out<ELFT>::VerNeed->getNeedNum()});
521   }
522 
523   if (Config->EMachine == EM_MIPS) {
524     Add({DT_MIPS_RLD_VERSION, 1});
525     Add({DT_MIPS_FLAGS, RHF_NOTPOT});
526     Add({DT_MIPS_BASE_ADDRESS, Config->ImageBase});
527     Add({DT_MIPS_SYMTABNO, Out<ELFT>::DynSymTab->getNumSymbols()});
528     Add({DT_MIPS_LOCAL_GOTNO, In<ELFT>::Got->getMipsLocalEntriesNum()});
529     if (const SymbolBody *B = In<ELFT>::Got->getMipsFirstGlobalEntry())
530       Add({DT_MIPS_GOTSYM, B->DynsymIndex});
531     else
532       Add({DT_MIPS_GOTSYM, Out<ELFT>::DynSymTab->getNumSymbols()});
533     Add({DT_PLTGOT, In<ELFT>::Got});
534     if (Out<ELFT>::MipsRldMap)
535       Add({DT_MIPS_RLD_MAP, Out<ELFT>::MipsRldMap});
536   }
537 
538   // +1 for DT_NULL
539   this->Size = (Entries.size() + 1) * this->Entsize;
540 }
541 
542 template <class ELFT> void DynamicSection<ELFT>::writeTo(uint8_t *Buf) {
543   auto *P = reinterpret_cast<Elf_Dyn *>(Buf);
544 
545   for (const Entry &E : Entries) {
546     P->d_tag = E.Tag;
547     switch (E.Kind) {
548     case Entry::SecAddr:
549       P->d_un.d_ptr = E.OutSec->Addr;
550       break;
551     case Entry::InSecAddr:
552       P->d_un.d_ptr = E.InSec->OutSec->Addr + E.InSec->OutSecOff;
553       break;
554     case Entry::SecSize:
555       P->d_un.d_val = E.OutSec->Size;
556       break;
557     case Entry::SymAddr:
558       P->d_un.d_ptr = E.Sym->template getVA<ELFT>();
559       break;
560     case Entry::PlainInt:
561       P->d_un.d_val = E.Val;
562       break;
563     }
564     ++P;
565   }
566 }
567 
568 template <class ELFT>
569 EhFrameHeader<ELFT>::EhFrameHeader()
570     : OutputSectionBase(".eh_frame_hdr", SHT_PROGBITS, SHF_ALLOC) {}
571 
572 // .eh_frame_hdr contains a binary search table of pointers to FDEs.
573 // Each entry of the search table consists of two values,
574 // the starting PC from where FDEs covers, and the FDE's address.
575 // It is sorted by PC.
576 template <class ELFT> void EhFrameHeader<ELFT>::writeTo(uint8_t *Buf) {
577   const endianness E = ELFT::TargetEndianness;
578 
579   // Sort the FDE list by their PC and uniqueify. Usually there is only
580   // one FDE for a PC (i.e. function), but if ICF merges two functions
581   // into one, there can be more than one FDEs pointing to the address.
582   auto Less = [](const FdeData &A, const FdeData &B) { return A.Pc < B.Pc; };
583   std::stable_sort(Fdes.begin(), Fdes.end(), Less);
584   auto Eq = [](const FdeData &A, const FdeData &B) { return A.Pc == B.Pc; };
585   Fdes.erase(std::unique(Fdes.begin(), Fdes.end(), Eq), Fdes.end());
586 
587   Buf[0] = 1;
588   Buf[1] = DW_EH_PE_pcrel | DW_EH_PE_sdata4;
589   Buf[2] = DW_EH_PE_udata4;
590   Buf[3] = DW_EH_PE_datarel | DW_EH_PE_sdata4;
591   write32<E>(Buf + 4, Out<ELFT>::EhFrame->Addr - this->Addr - 4);
592   write32<E>(Buf + 8, Fdes.size());
593   Buf += 12;
594 
595   uintX_t VA = this->Addr;
596   for (FdeData &Fde : Fdes) {
597     write32<E>(Buf, Fde.Pc - VA);
598     write32<E>(Buf + 4, Fde.FdeVA - VA);
599     Buf += 8;
600   }
601 }
602 
603 template <class ELFT> void EhFrameHeader<ELFT>::finalize() {
604   // .eh_frame_hdr has a 12 bytes header followed by an array of FDEs.
605   this->Size = 12 + Out<ELFT>::EhFrame->NumFdes * 8;
606 }
607 
608 template <class ELFT>
609 void EhFrameHeader<ELFT>::addFde(uint32_t Pc, uint32_t FdeVA) {
610   Fdes.push_back({Pc, FdeVA});
611 }
612 
613 template <class ELFT> static uint64_t getEntsize(uint32_t Type) {
614   switch (Type) {
615   case SHT_RELA:
616     return sizeof(typename ELFT::Rela);
617   case SHT_REL:
618     return sizeof(typename ELFT::Rel);
619   case SHT_MIPS_REGINFO:
620     return sizeof(Elf_Mips_RegInfo<ELFT>);
621   case SHT_MIPS_OPTIONS:
622     return sizeof(Elf_Mips_Options<ELFT>) + sizeof(Elf_Mips_RegInfo<ELFT>);
623   case SHT_MIPS_ABIFLAGS:
624     return sizeof(Elf_Mips_ABIFlags<ELFT>);
625   default:
626     return 0;
627   }
628 }
629 
630 template <class ELFT>
631 OutputSection<ELFT>::OutputSection(StringRef Name, uint32_t Type, uintX_t Flags)
632     : OutputSectionBase(Name, Type, Flags) {
633   this->Entsize = getEntsize<ELFT>(Type);
634 }
635 
636 template <class ELFT> void OutputSection<ELFT>::finalize() {
637   uint32_t Type = this->Type;
638   if (this->Flags & SHF_LINK_ORDER) {
639     if (!Config->Relocatable) {
640       // SHF_LINK_ORDER only has meaning in relocatable objects
641       this->Flags &= ~SHF_LINK_ORDER;
642     } else if (!this->Sections.empty()) {
643       // When doing a relocatable link we must preserve the link order
644       // dependency of sections with the SHF_LINK_ORDER flag. The dependency
645       // is indicated by the sh_link field. We need to translate the
646       // InputSection sh_link to the OutputSection sh_link, all InputSections
647       // in the OutputSection have the same dependency.
648       if (auto *D = this->Sections.front()->getLinkOrderDep())
649         this->Link = D->OutSec->SectionIndex;
650     }
651   }
652 
653   // Recalculate input section offsets if we own any synthetic section
654   for (auto *SS : In<ELFT>::SyntheticSections)
655     if (SS && this == SS->OutSec) {
656       this->Size = 0;
657       assignOffsets();
658       break;
659     }
660 
661   if (Type != SHT_RELA && Type != SHT_REL)
662     return;
663   this->Link = Out<ELFT>::SymTab->SectionIndex;
664   // sh_info for SHT_REL[A] sections should contain the section header index of
665   // the section to which the relocation applies.
666   InputSectionBase<ELFT> *S = Sections[0]->getRelocatedSection();
667   this->Info = S->OutSec->SectionIndex;
668 }
669 
670 template <class ELFT>
671 void OutputSection<ELFT>::addSection(InputSectionData *C) {
672   assert(C->Live);
673   auto *S = cast<InputSection<ELFT>>(C);
674   Sections.push_back(S);
675   S->OutSec = this;
676   this->updateAlignment(S->Alignment);
677   // Keep sh_entsize value of the input section to be able to perform merging
678   // later during a final linking using the generated relocatable object.
679   if (Config->Relocatable && (S->Flags & SHF_MERGE))
680     this->Entsize = S->Entsize;
681 }
682 
683 // This function is called after we sort input sections
684 // and scan relocations to setup sections' offsets.
685 template <class ELFT> void OutputSection<ELFT>::assignOffsets() {
686   uintX_t Off = this->Size;
687   for (InputSection<ELFT> *S : Sections) {
688     Off = alignTo(Off, S->Alignment);
689     S->OutSecOff = Off;
690     Off += S->getSize();
691   }
692   this->Size = Off;
693 }
694 
695 template <class ELFT>
696 void OutputSection<ELFT>::sort(
697     std::function<unsigned(InputSection<ELFT> *S)> Order) {
698   typedef std::pair<unsigned, InputSection<ELFT> *> Pair;
699   auto Comp = [](const Pair &A, const Pair &B) { return A.first < B.first; };
700 
701   std::vector<Pair> V;
702   for (InputSection<ELFT> *S : Sections)
703     V.push_back({Order(S), S});
704   std::stable_sort(V.begin(), V.end(), Comp);
705   Sections.clear();
706   for (Pair &P : V)
707     Sections.push_back(P.second);
708 }
709 
710 // Sorts input sections by section name suffixes, so that .foo.N comes
711 // before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
712 // We want to keep the original order if the priorities are the same
713 // because the compiler keeps the original initialization order in a
714 // translation unit and we need to respect that.
715 // For more detail, read the section of the GCC's manual about init_priority.
716 template <class ELFT> void OutputSection<ELFT>::sortInitFini() {
717   // Sort sections by priority.
718   sort([](InputSection<ELFT> *S) { return getPriority(S->Name); });
719 }
720 
721 // Returns true if S matches /Filename.?\.o$/.
722 static bool isCrtBeginEnd(StringRef S, StringRef Filename) {
723   if (!S.endswith(".o"))
724     return false;
725   S = S.drop_back(2);
726   if (S.endswith(Filename))
727     return true;
728   return !S.empty() && S.drop_back().endswith(Filename);
729 }
730 
731 static bool isCrtbegin(StringRef S) { return isCrtBeginEnd(S, "crtbegin"); }
732 static bool isCrtend(StringRef S) { return isCrtBeginEnd(S, "crtend"); }
733 
734 // .ctors and .dtors are sorted by this priority from highest to lowest.
735 //
736 //  1. The section was contained in crtbegin (crtbegin contains
737 //     some sentinel value in its .ctors and .dtors so that the runtime
738 //     can find the beginning of the sections.)
739 //
740 //  2. The section has an optional priority value in the form of ".ctors.N"
741 //     or ".dtors.N" where N is a number. Unlike .{init,fini}_array,
742 //     they are compared as string rather than number.
743 //
744 //  3. The section is just ".ctors" or ".dtors".
745 //
746 //  4. The section was contained in crtend, which contains an end marker.
747 //
748 // In an ideal world, we don't need this function because .init_array and
749 // .ctors are duplicate features (and .init_array is newer.) However, there
750 // are too many real-world use cases of .ctors, so we had no choice to
751 // support that with this rather ad-hoc semantics.
752 template <class ELFT>
753 static bool compCtors(const InputSection<ELFT> *A,
754                       const InputSection<ELFT> *B) {
755   bool BeginA = isCrtbegin(A->getFile()->getName());
756   bool BeginB = isCrtbegin(B->getFile()->getName());
757   if (BeginA != BeginB)
758     return BeginA;
759   bool EndA = isCrtend(A->getFile()->getName());
760   bool EndB = isCrtend(B->getFile()->getName());
761   if (EndA != EndB)
762     return EndB;
763   StringRef X = A->Name;
764   StringRef Y = B->Name;
765   assert(X.startswith(".ctors") || X.startswith(".dtors"));
766   assert(Y.startswith(".ctors") || Y.startswith(".dtors"));
767   X = X.substr(6);
768   Y = Y.substr(6);
769   if (X.empty() && Y.empty())
770     return false;
771   return X < Y;
772 }
773 
774 // Sorts input sections by the special rules for .ctors and .dtors.
775 // Unfortunately, the rules are different from the one for .{init,fini}_array.
776 // Read the comment above.
777 template <class ELFT> void OutputSection<ELFT>::sortCtorsDtors() {
778   std::stable_sort(Sections.begin(), Sections.end(), compCtors<ELFT>);
779 }
780 
781 static void fill(uint8_t *Buf, size_t Size, ArrayRef<uint8_t> A) {
782   size_t I = 0;
783   for (; I + A.size() < Size; I += A.size())
784     memcpy(Buf + I, A.data(), A.size());
785   memcpy(Buf + I, A.data(), Size - I);
786 }
787 
788 template <class ELFT> void OutputSection<ELFT>::writeTo(uint8_t *Buf) {
789   ArrayRef<uint8_t> Filler = Script<ELFT>::X->getFiller(this->Name);
790   if (!Filler.empty())
791     fill(Buf, this->Size, Filler);
792   if (Config->Threads) {
793     parallel_for_each(Sections.begin(), Sections.end(),
794                       [=](InputSection<ELFT> *C) { C->writeTo(Buf); });
795   } else {
796     for (InputSection<ELFT> *C : Sections)
797       C->writeTo(Buf);
798   }
799   // Linker scripts may have BYTE()-family commands with which you
800   // can write arbitrary bytes to the output. Process them if any.
801   Script<ELFT>::X->writeDataBytes(this->Name, Buf);
802 }
803 
804 template <class ELFT>
805 EhOutputSection<ELFT>::EhOutputSection()
806     : OutputSectionBase(".eh_frame", SHT_PROGBITS, SHF_ALLOC) {}
807 
808 // Search for an existing CIE record or create a new one.
809 // CIE records from input object files are uniquified by their contents
810 // and where their relocations point to.
811 template <class ELFT>
812 template <class RelTy>
813 CieRecord *EhOutputSection<ELFT>::addCie(EhSectionPiece &Piece,
814                                          EhInputSection<ELFT> *Sec,
815                                          ArrayRef<RelTy> Rels) {
816   const endianness E = ELFT::TargetEndianness;
817   if (read32<E>(Piece.data().data() + 4) != 0)
818     fatal("CIE expected at beginning of .eh_frame: " + Sec->Name);
819 
820   SymbolBody *Personality = nullptr;
821   unsigned FirstRelI = Piece.FirstRelocation;
822   if (FirstRelI != (unsigned)-1)
823     Personality = &Sec->getFile()->getRelocTargetSym(Rels[FirstRelI]);
824 
825   // Search for an existing CIE by CIE contents/relocation target pair.
826   CieRecord *Cie = &CieMap[{Piece.data(), Personality}];
827 
828   // If not found, create a new one.
829   if (Cie->Piece == nullptr) {
830     Cie->Piece = &Piece;
831     Cies.push_back(Cie);
832   }
833   return Cie;
834 }
835 
836 // There is one FDE per function. Returns true if a given FDE
837 // points to a live function.
838 template <class ELFT>
839 template <class RelTy>
840 bool EhOutputSection<ELFT>::isFdeLive(EhSectionPiece &Piece,
841                                       EhInputSection<ELFT> *Sec,
842                                       ArrayRef<RelTy> Rels) {
843   unsigned FirstRelI = Piece.FirstRelocation;
844   if (FirstRelI == (unsigned)-1)
845     fatal("FDE doesn't reference another section");
846   const RelTy &Rel = Rels[FirstRelI];
847   SymbolBody &B = Sec->getFile()->getRelocTargetSym(Rel);
848   auto *D = dyn_cast<DefinedRegular<ELFT>>(&B);
849   if (!D || !D->Section)
850     return false;
851   InputSectionBase<ELFT> *Target = D->Section->Repl;
852   return Target && Target->Live;
853 }
854 
855 // .eh_frame is a sequence of CIE or FDE records. In general, there
856 // is one CIE record per input object file which is followed by
857 // a list of FDEs. This function searches an existing CIE or create a new
858 // one and associates FDEs to the CIE.
859 template <class ELFT>
860 template <class RelTy>
861 void EhOutputSection<ELFT>::addSectionAux(EhInputSection<ELFT> *Sec,
862                                           ArrayRef<RelTy> Rels) {
863   const endianness E = ELFT::TargetEndianness;
864 
865   DenseMap<size_t, CieRecord *> OffsetToCie;
866   for (EhSectionPiece &Piece : Sec->Pieces) {
867     // The empty record is the end marker.
868     if (Piece.size() == 4)
869       return;
870 
871     size_t Offset = Piece.InputOff;
872     uint32_t ID = read32<E>(Piece.data().data() + 4);
873     if (ID == 0) {
874       OffsetToCie[Offset] = addCie(Piece, Sec, Rels);
875       continue;
876     }
877 
878     uint32_t CieOffset = Offset + 4 - ID;
879     CieRecord *Cie = OffsetToCie[CieOffset];
880     if (!Cie)
881       fatal("invalid CIE reference");
882 
883     if (!isFdeLive(Piece, Sec, Rels))
884       continue;
885     Cie->FdePieces.push_back(&Piece);
886     NumFdes++;
887   }
888 }
889 
890 template <class ELFT>
891 void EhOutputSection<ELFT>::addSection(InputSectionData *C) {
892   auto *Sec = cast<EhInputSection<ELFT>>(C);
893   Sec->OutSec = this;
894   this->updateAlignment(Sec->Alignment);
895   Sections.push_back(Sec);
896 
897   // .eh_frame is a sequence of CIE or FDE records. This function
898   // splits it into pieces so that we can call
899   // SplitInputSection::getSectionPiece on the section.
900   Sec->split();
901   if (Sec->Pieces.empty())
902     return;
903 
904   if (Sec->NumRelocations) {
905     if (Sec->AreRelocsRela)
906       addSectionAux(Sec, Sec->relas());
907     else
908       addSectionAux(Sec, Sec->rels());
909     return;
910   }
911   addSectionAux(Sec, makeArrayRef<Elf_Rela>(nullptr, nullptr));
912 }
913 
914 template <class ELFT>
915 static void writeCieFde(uint8_t *Buf, ArrayRef<uint8_t> D) {
916   memcpy(Buf, D.data(), D.size());
917 
918   // Fix the size field. -4 since size does not include the size field itself.
919   const endianness E = ELFT::TargetEndianness;
920   write32<E>(Buf, alignTo(D.size(), sizeof(typename ELFT::uint)) - 4);
921 }
922 
923 template <class ELFT> void EhOutputSection<ELFT>::finalize() {
924   if (this->Size)
925     return; // Already finalized.
926 
927   size_t Off = 0;
928   for (CieRecord *Cie : Cies) {
929     Cie->Piece->OutputOff = Off;
930     Off += alignTo(Cie->Piece->size(), sizeof(uintX_t));
931 
932     for (EhSectionPiece *Fde : Cie->FdePieces) {
933       Fde->OutputOff = Off;
934       Off += alignTo(Fde->size(), sizeof(uintX_t));
935     }
936   }
937   this->Size = Off;
938 }
939 
940 template <class ELFT> static uint64_t readFdeAddr(uint8_t *Buf, int Size) {
941   const endianness E = ELFT::TargetEndianness;
942   switch (Size) {
943   case DW_EH_PE_udata2:
944     return read16<E>(Buf);
945   case DW_EH_PE_udata4:
946     return read32<E>(Buf);
947   case DW_EH_PE_udata8:
948     return read64<E>(Buf);
949   case DW_EH_PE_absptr:
950     if (ELFT::Is64Bits)
951       return read64<E>(Buf);
952     return read32<E>(Buf);
953   }
954   fatal("unknown FDE size encoding");
955 }
956 
957 // Returns the VA to which a given FDE (on a mmap'ed buffer) is applied to.
958 // We need it to create .eh_frame_hdr section.
959 template <class ELFT>
960 typename ELFT::uint EhOutputSection<ELFT>::getFdePc(uint8_t *Buf, size_t FdeOff,
961                                                     uint8_t Enc) {
962   // The starting address to which this FDE applies is
963   // stored at FDE + 8 byte.
964   size_t Off = FdeOff + 8;
965   uint64_t Addr = readFdeAddr<ELFT>(Buf + Off, Enc & 0x7);
966   if ((Enc & 0x70) == DW_EH_PE_absptr)
967     return Addr;
968   if ((Enc & 0x70) == DW_EH_PE_pcrel)
969     return Addr + this->Addr + Off;
970   fatal("unknown FDE size relative encoding");
971 }
972 
973 template <class ELFT> void EhOutputSection<ELFT>::writeTo(uint8_t *Buf) {
974   const endianness E = ELFT::TargetEndianness;
975   for (CieRecord *Cie : Cies) {
976     size_t CieOffset = Cie->Piece->OutputOff;
977     writeCieFde<ELFT>(Buf + CieOffset, Cie->Piece->data());
978 
979     for (EhSectionPiece *Fde : Cie->FdePieces) {
980       size_t Off = Fde->OutputOff;
981       writeCieFde<ELFT>(Buf + Off, Fde->data());
982 
983       // FDE's second word should have the offset to an associated CIE.
984       // Write it.
985       write32<E>(Buf + Off + 4, Off + 4 - CieOffset);
986     }
987   }
988 
989   for (EhInputSection<ELFT> *S : Sections)
990     S->relocate(Buf, nullptr);
991 
992   // Construct .eh_frame_hdr. .eh_frame_hdr is a binary search table
993   // to get a FDE from an address to which FDE is applied. So here
994   // we obtain two addresses and pass them to EhFrameHdr object.
995   if (Out<ELFT>::EhFrameHdr) {
996     for (CieRecord *Cie : Cies) {
997       uint8_t Enc = getFdeEncoding<ELFT>(Cie->Piece->data());
998       for (SectionPiece *Fde : Cie->FdePieces) {
999         uintX_t Pc = getFdePc(Buf, Fde->OutputOff, Enc);
1000         uintX_t FdeVA = this->Addr + Fde->OutputOff;
1001         Out<ELFT>::EhFrameHdr->addFde(Pc, FdeVA);
1002       }
1003     }
1004   }
1005 }
1006 
1007 template <class ELFT>
1008 MergeOutputSection<ELFT>::MergeOutputSection(StringRef Name, uint32_t Type,
1009                                              uintX_t Flags, uintX_t Alignment)
1010     : OutputSectionBase(Name, Type, Flags),
1011       Builder(StringTableBuilder::RAW, Alignment) {}
1012 
1013 template <class ELFT> void MergeOutputSection<ELFT>::writeTo(uint8_t *Buf) {
1014   Builder.write(Buf);
1015 }
1016 
1017 template <class ELFT>
1018 void MergeOutputSection<ELFT>::addSection(InputSectionData *C) {
1019   auto *Sec = cast<MergeInputSection<ELFT>>(C);
1020   Sec->OutSec = this;
1021   this->updateAlignment(Sec->Alignment);
1022   this->Entsize = Sec->Entsize;
1023   Sections.push_back(Sec);
1024 
1025   auto HashI = Sec->Hashes.begin();
1026   for (auto I = Sec->Pieces.begin(), E = Sec->Pieces.end(); I != E; ++I) {
1027     SectionPiece &Piece = *I;
1028     uint32_t Hash = *HashI;
1029     ++HashI;
1030     if (!Piece.Live)
1031       continue;
1032     StringRef Data = toStringRef(Sec->getData(I));
1033     CachedHashStringRef V(Data, Hash);
1034     uintX_t OutputOffset = Builder.add(V);
1035     if (!shouldTailMerge())
1036       Piece.OutputOff = OutputOffset;
1037   }
1038 }
1039 
1040 template <class ELFT>
1041 unsigned MergeOutputSection<ELFT>::getOffset(CachedHashStringRef Val) {
1042   return Builder.getOffset(Val);
1043 }
1044 
1045 template <class ELFT> bool MergeOutputSection<ELFT>::shouldTailMerge() const {
1046   return Config->Optimize >= 2 && this->Flags & SHF_STRINGS;
1047 }
1048 
1049 template <class ELFT> void MergeOutputSection<ELFT>::finalize() {
1050   if (shouldTailMerge())
1051     Builder.finalize();
1052   else
1053     Builder.finalizeInOrder();
1054   this->Size = Builder.getSize();
1055 }
1056 
1057 template <class ELFT> void MergeOutputSection<ELFT>::finalizePieces() {
1058   for (MergeInputSection<ELFT> *Sec : Sections)
1059     Sec->finalizePieces();
1060 }
1061 
1062 template <class ELFT>
1063 typename ELFT::uint DynamicReloc<ELFT>::getOffset() const {
1064   if (OutputSec)
1065     return OutputSec->Addr + OffsetInSec;
1066   return InputSec->OutSec->Addr + InputSec->getOffset(OffsetInSec);
1067 }
1068 
1069 template <class ELFT>
1070 typename ELFT::uint DynamicReloc<ELFT>::getAddend() const {
1071   if (UseSymVA)
1072     return Sym->getVA<ELFT>(Addend);
1073   return Addend;
1074 }
1075 
1076 template <class ELFT> uint32_t DynamicReloc<ELFT>::getSymIndex() const {
1077   if (Sym && !UseSymVA)
1078     return Sym->DynsymIndex;
1079   return 0;
1080 }
1081 
1082 template <class ELFT>
1083 SymbolTableSection<ELFT>::SymbolTableSection(
1084     StringTableSection<ELFT> &StrTabSec)
1085     : OutputSectionBase(StrTabSec.isDynamic() ? ".dynsym" : ".symtab",
1086                         StrTabSec.isDynamic() ? SHT_DYNSYM : SHT_SYMTAB,
1087                         StrTabSec.isDynamic() ? (uintX_t)SHF_ALLOC : 0),
1088       StrTabSec(StrTabSec) {
1089   this->Entsize = sizeof(Elf_Sym);
1090   this->Addralign = sizeof(uintX_t);
1091 }
1092 
1093 // Orders symbols according to their positions in the GOT,
1094 // in compliance with MIPS ABI rules.
1095 // See "Global Offset Table" in Chapter 5 in the following document
1096 // for detailed description:
1097 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
1098 static bool sortMipsSymbols(const SymbolBody *L, const SymbolBody *R) {
1099   // Sort entries related to non-local preemptible symbols by GOT indexes.
1100   // All other entries go to the first part of GOT in arbitrary order.
1101   bool LIsInLocalGot = !L->IsInGlobalMipsGot;
1102   bool RIsInLocalGot = !R->IsInGlobalMipsGot;
1103   if (LIsInLocalGot || RIsInLocalGot)
1104     return !RIsInLocalGot;
1105   return L->GotIndex < R->GotIndex;
1106 }
1107 
1108 static uint8_t getSymbolBinding(SymbolBody *Body) {
1109   Symbol *S = Body->symbol();
1110   if (Config->Relocatable)
1111     return S->Binding;
1112   uint8_t Visibility = S->Visibility;
1113   if (Visibility != STV_DEFAULT && Visibility != STV_PROTECTED)
1114     return STB_LOCAL;
1115   if (Config->NoGnuUnique && S->Binding == STB_GNU_UNIQUE)
1116     return STB_GLOBAL;
1117   return S->Binding;
1118 }
1119 
1120 template <class ELFT> void SymbolTableSection<ELFT>::finalize() {
1121   if (this->Size)
1122     return; // Already finalized.
1123 
1124   this->Size = getNumSymbols() * sizeof(Elf_Sym);
1125   this->Link = StrTabSec.OutSec->SectionIndex;
1126   this->Info = NumLocals + 1;
1127 
1128   if (Config->Relocatable) {
1129     size_t I = NumLocals;
1130     for (const SymbolTableEntry &S : Symbols)
1131       S.Symbol->DynsymIndex = ++I;
1132     return;
1133   }
1134 
1135   if (!StrTabSec.isDynamic()) {
1136     std::stable_sort(Symbols.begin(), Symbols.end(),
1137                      [](const SymbolTableEntry &L, const SymbolTableEntry &R) {
1138                        return getSymbolBinding(L.Symbol) == STB_LOCAL &&
1139                               getSymbolBinding(R.Symbol) != STB_LOCAL;
1140                      });
1141     return;
1142   }
1143   if (Out<ELFT>::GnuHashTab)
1144     // NB: It also sorts Symbols to meet the GNU hash table requirements.
1145     Out<ELFT>::GnuHashTab->addSymbols(Symbols);
1146   else if (Config->EMachine == EM_MIPS)
1147     std::stable_sort(Symbols.begin(), Symbols.end(),
1148                      [](const SymbolTableEntry &L, const SymbolTableEntry &R) {
1149                        return sortMipsSymbols(L.Symbol, R.Symbol);
1150                      });
1151   size_t I = 0;
1152   for (const SymbolTableEntry &S : Symbols)
1153     S.Symbol->DynsymIndex = ++I;
1154 }
1155 
1156 template <class ELFT> void SymbolTableSection<ELFT>::addSymbol(SymbolBody *B) {
1157   Symbols.push_back({B, StrTabSec.addString(B->getName(), false)});
1158 }
1159 
1160 template <class ELFT> void SymbolTableSection<ELFT>::writeTo(uint8_t *Buf) {
1161   Buf += sizeof(Elf_Sym);
1162 
1163   // All symbols with STB_LOCAL binding precede the weak and global symbols.
1164   // .dynsym only contains global symbols.
1165   if (Config->Discard != DiscardPolicy::All && !StrTabSec.isDynamic())
1166     writeLocalSymbols(Buf);
1167 
1168   writeGlobalSymbols(Buf);
1169 }
1170 
1171 template <class ELFT>
1172 void SymbolTableSection<ELFT>::writeLocalSymbols(uint8_t *&Buf) {
1173   // Iterate over all input object files to copy their local symbols
1174   // to the output symbol table pointed by Buf.
1175   for (ObjectFile<ELFT> *File : Symtab<ELFT>::X->getObjectFiles()) {
1176     for (const std::pair<const DefinedRegular<ELFT> *, size_t> &P :
1177          File->KeptLocalSyms) {
1178       const DefinedRegular<ELFT> &Body = *P.first;
1179       InputSectionBase<ELFT> *Section = Body.Section;
1180       auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
1181 
1182       if (!Section) {
1183         ESym->st_shndx = SHN_ABS;
1184         ESym->st_value = Body.Value;
1185       } else {
1186         const OutputSectionBase *OutSec = Section->OutSec;
1187         ESym->st_shndx = OutSec->SectionIndex;
1188         ESym->st_value = OutSec->Addr + Section->getOffset(Body);
1189       }
1190       ESym->st_name = P.second;
1191       ESym->st_size = Body.template getSize<ELFT>();
1192       ESym->setBindingAndType(STB_LOCAL, Body.Type);
1193       Buf += sizeof(*ESym);
1194     }
1195   }
1196 }
1197 
1198 template <class ELFT>
1199 void SymbolTableSection<ELFT>::writeGlobalSymbols(uint8_t *Buf) {
1200   // Write the internal symbol table contents to the output symbol table
1201   // pointed by Buf.
1202   auto *ESym = reinterpret_cast<Elf_Sym *>(Buf);
1203   for (const SymbolTableEntry &S : Symbols) {
1204     SymbolBody *Body = S.Symbol;
1205     size_t StrOff = S.StrTabOffset;
1206 
1207     uint8_t Type = Body->Type;
1208     uintX_t Size = Body->getSize<ELFT>();
1209 
1210     ESym->setBindingAndType(getSymbolBinding(Body), Type);
1211     ESym->st_size = Size;
1212     ESym->st_name = StrOff;
1213     ESym->setVisibility(Body->symbol()->Visibility);
1214     ESym->st_value = Body->getVA<ELFT>();
1215 
1216     if (const OutputSectionBase *OutSec = getOutputSection(Body))
1217       ESym->st_shndx = OutSec->SectionIndex;
1218     else if (isa<DefinedRegular<ELFT>>(Body))
1219       ESym->st_shndx = SHN_ABS;
1220 
1221     if (Config->EMachine == EM_MIPS) {
1222       // On MIPS we need to mark symbol which has a PLT entry and requires
1223       // pointer equality by STO_MIPS_PLT flag. That is necessary to help
1224       // dynamic linker distinguish such symbols and MIPS lazy-binding stubs.
1225       // https://sourceware.org/ml/binutils/2008-07/txt00000.txt
1226       if (Body->isInPlt() && Body->NeedsCopyOrPltAddr)
1227         ESym->st_other |= STO_MIPS_PLT;
1228       if (Config->Relocatable) {
1229         auto *D = dyn_cast<DefinedRegular<ELFT>>(Body);
1230         if (D && D->isMipsPIC())
1231           ESym->st_other |= STO_MIPS_PIC;
1232       }
1233     }
1234     ++ESym;
1235   }
1236 }
1237 
1238 template <class ELFT>
1239 const OutputSectionBase *
1240 SymbolTableSection<ELFT>::getOutputSection(SymbolBody *Sym) {
1241   switch (Sym->kind()) {
1242   case SymbolBody::DefinedSyntheticKind:
1243     return cast<DefinedSynthetic<ELFT>>(Sym)->Section;
1244   case SymbolBody::DefinedRegularKind: {
1245     auto &D = cast<DefinedRegular<ELFT>>(*Sym);
1246     if (D.Section)
1247       return D.Section->OutSec;
1248     break;
1249   }
1250   case SymbolBody::DefinedCommonKind:
1251     return In<ELFT>::Common->OutSec;
1252   case SymbolBody::SharedKind:
1253     if (cast<SharedSymbol<ELFT>>(Sym)->needsCopy())
1254       return Out<ELFT>::Bss;
1255     break;
1256   case SymbolBody::UndefinedKind:
1257   case SymbolBody::LazyArchiveKind:
1258   case SymbolBody::LazyObjectKind:
1259     break;
1260   }
1261   return nullptr;
1262 }
1263 
1264 template <class ELFT>
1265 VersionDefinitionSection<ELFT>::VersionDefinitionSection()
1266     : OutputSectionBase(".gnu.version_d", SHT_GNU_verdef, SHF_ALLOC) {
1267   this->Addralign = sizeof(uint32_t);
1268 }
1269 
1270 static StringRef getFileDefName() {
1271   if (!Config->SoName.empty())
1272     return Config->SoName;
1273   return Config->OutputFile;
1274 }
1275 
1276 template <class ELFT> void VersionDefinitionSection<ELFT>::finalize() {
1277   FileDefNameOff = In<ELFT>::DynStrTab->addString(getFileDefName());
1278   for (VersionDefinition &V : Config->VersionDefinitions)
1279     V.NameOff = In<ELFT>::DynStrTab->addString(V.Name);
1280 
1281   this->Size = (sizeof(Elf_Verdef) + sizeof(Elf_Verdaux)) * getVerDefNum();
1282   this->Link = In<ELFT>::DynStrTab->OutSec->SectionIndex;
1283 
1284   // sh_info should be set to the number of definitions. This fact is missed in
1285   // documentation, but confirmed by binutils community:
1286   // https://sourceware.org/ml/binutils/2014-11/msg00355.html
1287   this->Info = getVerDefNum();
1288 }
1289 
1290 template <class ELFT>
1291 void VersionDefinitionSection<ELFT>::writeOne(uint8_t *Buf, uint32_t Index,
1292                                               StringRef Name, size_t NameOff) {
1293   auto *Verdef = reinterpret_cast<Elf_Verdef *>(Buf);
1294   Verdef->vd_version = 1;
1295   Verdef->vd_cnt = 1;
1296   Verdef->vd_aux = sizeof(Elf_Verdef);
1297   Verdef->vd_next = sizeof(Elf_Verdef) + sizeof(Elf_Verdaux);
1298   Verdef->vd_flags = (Index == 1 ? VER_FLG_BASE : 0);
1299   Verdef->vd_ndx = Index;
1300   Verdef->vd_hash = hashSysV(Name);
1301 
1302   auto *Verdaux = reinterpret_cast<Elf_Verdaux *>(Buf + sizeof(Elf_Verdef));
1303   Verdaux->vda_name = NameOff;
1304   Verdaux->vda_next = 0;
1305 }
1306 
1307 template <class ELFT>
1308 void VersionDefinitionSection<ELFT>::writeTo(uint8_t *Buf) {
1309   writeOne(Buf, 1, getFileDefName(), FileDefNameOff);
1310 
1311   for (VersionDefinition &V : Config->VersionDefinitions) {
1312     Buf += sizeof(Elf_Verdef) + sizeof(Elf_Verdaux);
1313     writeOne(Buf, V.Id, V.Name, V.NameOff);
1314   }
1315 
1316   // Need to terminate the last version definition.
1317   Elf_Verdef *Verdef = reinterpret_cast<Elf_Verdef *>(Buf);
1318   Verdef->vd_next = 0;
1319 }
1320 
1321 template <class ELFT>
1322 VersionTableSection<ELFT>::VersionTableSection()
1323     : OutputSectionBase(".gnu.version", SHT_GNU_versym, SHF_ALLOC) {
1324   this->Addralign = sizeof(uint16_t);
1325 }
1326 
1327 template <class ELFT> void VersionTableSection<ELFT>::finalize() {
1328   this->Size =
1329       sizeof(Elf_Versym) * (Out<ELFT>::DynSymTab->getSymbols().size() + 1);
1330   this->Entsize = sizeof(Elf_Versym);
1331   // At the moment of june 2016 GNU docs does not mention that sh_link field
1332   // should be set, but Sun docs do. Also readelf relies on this field.
1333   this->Link = Out<ELFT>::DynSymTab->SectionIndex;
1334 }
1335 
1336 template <class ELFT> void VersionTableSection<ELFT>::writeTo(uint8_t *Buf) {
1337   auto *OutVersym = reinterpret_cast<Elf_Versym *>(Buf) + 1;
1338   for (const SymbolTableEntry &S : Out<ELFT>::DynSymTab->getSymbols()) {
1339     OutVersym->vs_index = S.Symbol->symbol()->VersionId;
1340     ++OutVersym;
1341   }
1342 }
1343 
1344 template <class ELFT>
1345 VersionNeedSection<ELFT>::VersionNeedSection()
1346     : OutputSectionBase(".gnu.version_r", SHT_GNU_verneed, SHF_ALLOC) {
1347   this->Addralign = sizeof(uint32_t);
1348 
1349   // Identifiers in verneed section start at 2 because 0 and 1 are reserved
1350   // for VER_NDX_LOCAL and VER_NDX_GLOBAL.
1351   // First identifiers are reserved by verdef section if it exist.
1352   NextIndex = getVerDefNum() + 1;
1353 }
1354 
1355 template <class ELFT>
1356 void VersionNeedSection<ELFT>::addSymbol(SharedSymbol<ELFT> *SS) {
1357   if (!SS->Verdef) {
1358     SS->symbol()->VersionId = VER_NDX_GLOBAL;
1359     return;
1360   }
1361   SharedFile<ELFT> *F = SS->file();
1362   // If we don't already know that we need an Elf_Verneed for this DSO, prepare
1363   // to create one by adding it to our needed list and creating a dynstr entry
1364   // for the soname.
1365   if (F->VerdefMap.empty())
1366     Needed.push_back({F, In<ELFT>::DynStrTab->addString(F->getSoName())});
1367   typename SharedFile<ELFT>::NeededVer &NV = F->VerdefMap[SS->Verdef];
1368   // If we don't already know that we need an Elf_Vernaux for this Elf_Verdef,
1369   // prepare to create one by allocating a version identifier and creating a
1370   // dynstr entry for the version name.
1371   if (NV.Index == 0) {
1372     NV.StrTab = In<ELFT>::DynStrTab->addString(
1373         SS->file()->getStringTable().data() + SS->Verdef->getAux()->vda_name);
1374     NV.Index = NextIndex++;
1375   }
1376   SS->symbol()->VersionId = NV.Index;
1377 }
1378 
1379 template <class ELFT> void VersionNeedSection<ELFT>::writeTo(uint8_t *Buf) {
1380   // The Elf_Verneeds need to appear first, followed by the Elf_Vernauxs.
1381   auto *Verneed = reinterpret_cast<Elf_Verneed *>(Buf);
1382   auto *Vernaux = reinterpret_cast<Elf_Vernaux *>(Verneed + Needed.size());
1383 
1384   for (std::pair<SharedFile<ELFT> *, size_t> &P : Needed) {
1385     // Create an Elf_Verneed for this DSO.
1386     Verneed->vn_version = 1;
1387     Verneed->vn_cnt = P.first->VerdefMap.size();
1388     Verneed->vn_file = P.second;
1389     Verneed->vn_aux =
1390         reinterpret_cast<char *>(Vernaux) - reinterpret_cast<char *>(Verneed);
1391     Verneed->vn_next = sizeof(Elf_Verneed);
1392     ++Verneed;
1393 
1394     // Create the Elf_Vernauxs for this Elf_Verneed. The loop iterates over
1395     // VerdefMap, which will only contain references to needed version
1396     // definitions. Each Elf_Vernaux is based on the information contained in
1397     // the Elf_Verdef in the source DSO. This loop iterates over a std::map of
1398     // pointers, but is deterministic because the pointers refer to Elf_Verdef
1399     // data structures within a single input file.
1400     for (auto &NV : P.first->VerdefMap) {
1401       Vernaux->vna_hash = NV.first->vd_hash;
1402       Vernaux->vna_flags = 0;
1403       Vernaux->vna_other = NV.second.Index;
1404       Vernaux->vna_name = NV.second.StrTab;
1405       Vernaux->vna_next = sizeof(Elf_Vernaux);
1406       ++Vernaux;
1407     }
1408 
1409     Vernaux[-1].vna_next = 0;
1410   }
1411   Verneed[-1].vn_next = 0;
1412 }
1413 
1414 template <class ELFT> void VersionNeedSection<ELFT>::finalize() {
1415   this->Link = In<ELFT>::DynStrTab->OutSec->SectionIndex;
1416   this->Info = Needed.size();
1417   unsigned Size = Needed.size() * sizeof(Elf_Verneed);
1418   for (std::pair<SharedFile<ELFT> *, size_t> &P : Needed)
1419     Size += P.first->VerdefMap.size() * sizeof(Elf_Vernaux);
1420   this->Size = Size;
1421 }
1422 
1423 template <class ELFT>
1424 static typename ELFT::uint getOutFlags(InputSectionBase<ELFT> *S) {
1425   return S->Flags & ~SHF_GROUP & ~SHF_COMPRESSED;
1426 }
1427 
1428 template <class ELFT>
1429 static SectionKey<ELFT::Is64Bits> createKey(InputSectionBase<ELFT> *C,
1430                                             StringRef OutsecName) {
1431   typedef typename ELFT::uint uintX_t;
1432   uintX_t Flags = getOutFlags(C);
1433 
1434   // For SHF_MERGE we create different output sections for each alignment.
1435   // This makes each output section simple and keeps a single level mapping from
1436   // input to output.
1437   // In case of relocatable object generation we do not try to perform merging
1438   // and treat SHF_MERGE sections as regular ones, but also create different
1439   // output sections for them to allow merging at final linking stage.
1440   uintX_t Alignment = 0;
1441   if (isa<MergeInputSection<ELFT>>(C) ||
1442       (Config->Relocatable && (C->Flags & SHF_MERGE)))
1443     Alignment = std::max<uintX_t>(C->Alignment, C->Entsize);
1444 
1445   return SectionKey<ELFT::Is64Bits>{OutsecName, C->Type, Flags, Alignment};
1446 }
1447 
1448 template <class ELFT>
1449 std::pair<OutputSectionBase *, bool>
1450 OutputSectionFactory<ELFT>::create(InputSectionBase<ELFT> *C,
1451                                    StringRef OutsecName) {
1452   SectionKey<ELFT::Is64Bits> Key = createKey(C, OutsecName);
1453   return create(Key, C);
1454 }
1455 
1456 template <class ELFT>
1457 std::pair<OutputSectionBase *, bool>
1458 OutputSectionFactory<ELFT>::create(const SectionKey<ELFT::Is64Bits> &Key,
1459                                    InputSectionBase<ELFT> *C) {
1460   uintX_t Flags = getOutFlags(C);
1461   OutputSectionBase *&Sec = Map[Key];
1462   if (Sec) {
1463     Sec->Flags |= Flags;
1464     return {Sec, false};
1465   }
1466 
1467   uint32_t Type = C->Type;
1468   switch (C->kind()) {
1469   case InputSectionBase<ELFT>::Regular:
1470   case InputSectionBase<ELFT>::Synthetic:
1471     Sec = make<OutputSection<ELFT>>(Key.Name, Type, Flags);
1472     break;
1473   case InputSectionBase<ELFT>::EHFrame:
1474     return {Out<ELFT>::EhFrame, false};
1475   case InputSectionBase<ELFT>::Merge:
1476     Sec = make<MergeOutputSection<ELFT>>(Key.Name, Type, Flags, Key.Alignment);
1477     break;
1478   }
1479   return {Sec, true};
1480 }
1481 
1482 template <bool Is64Bits>
1483 typename lld::elf::SectionKey<Is64Bits>
1484 DenseMapInfo<lld::elf::SectionKey<Is64Bits>>::getEmptyKey() {
1485   return SectionKey<Is64Bits>{DenseMapInfo<StringRef>::getEmptyKey(), 0, 0, 0};
1486 }
1487 
1488 template <bool Is64Bits>
1489 typename lld::elf::SectionKey<Is64Bits>
1490 DenseMapInfo<lld::elf::SectionKey<Is64Bits>>::getTombstoneKey() {
1491   return SectionKey<Is64Bits>{DenseMapInfo<StringRef>::getTombstoneKey(), 0, 0,
1492                               0};
1493 }
1494 
1495 template <bool Is64Bits>
1496 unsigned
1497 DenseMapInfo<lld::elf::SectionKey<Is64Bits>>::getHashValue(const Key &Val) {
1498   return hash_combine(Val.Name, Val.Type, Val.Flags, Val.Alignment);
1499 }
1500 
1501 template <bool Is64Bits>
1502 bool DenseMapInfo<lld::elf::SectionKey<Is64Bits>>::isEqual(const Key &LHS,
1503                                                            const Key &RHS) {
1504   return DenseMapInfo<StringRef>::isEqual(LHS.Name, RHS.Name) &&
1505          LHS.Type == RHS.Type && LHS.Flags == RHS.Flags &&
1506          LHS.Alignment == RHS.Alignment;
1507 }
1508 
1509 namespace llvm {
1510 template struct DenseMapInfo<SectionKey<true>>;
1511 template struct DenseMapInfo<SectionKey<false>>;
1512 }
1513 
1514 namespace lld {
1515 namespace elf {
1516 
1517 template void OutputSectionBase::writeHeaderTo<ELF32LE>(ELF32LE::Shdr *Shdr);
1518 template void OutputSectionBase::writeHeaderTo<ELF32BE>(ELF32BE::Shdr *Shdr);
1519 template void OutputSectionBase::writeHeaderTo<ELF64LE>(ELF64LE::Shdr *Shdr);
1520 template void OutputSectionBase::writeHeaderTo<ELF64BE>(ELF64BE::Shdr *Shdr);
1521 
1522 template class EhFrameHeader<ELF32LE>;
1523 template class EhFrameHeader<ELF32BE>;
1524 template class EhFrameHeader<ELF64LE>;
1525 template class EhFrameHeader<ELF64BE>;
1526 
1527 template class PltSection<ELF32LE>;
1528 template class PltSection<ELF32BE>;
1529 template class PltSection<ELF64LE>;
1530 template class PltSection<ELF64BE>;
1531 
1532 template class RelocationSection<ELF32LE>;
1533 template class RelocationSection<ELF32BE>;
1534 template class RelocationSection<ELF64LE>;
1535 template class RelocationSection<ELF64BE>;
1536 
1537 template class GnuHashTableSection<ELF32LE>;
1538 template class GnuHashTableSection<ELF32BE>;
1539 template class GnuHashTableSection<ELF64LE>;
1540 template class GnuHashTableSection<ELF64BE>;
1541 
1542 template class HashTableSection<ELF32LE>;
1543 template class HashTableSection<ELF32BE>;
1544 template class HashTableSection<ELF64LE>;
1545 template class HashTableSection<ELF64BE>;
1546 
1547 template class DynamicSection<ELF32LE>;
1548 template class DynamicSection<ELF32BE>;
1549 template class DynamicSection<ELF64LE>;
1550 template class DynamicSection<ELF64BE>;
1551 
1552 template class OutputSection<ELF32LE>;
1553 template class OutputSection<ELF32BE>;
1554 template class OutputSection<ELF64LE>;
1555 template class OutputSection<ELF64BE>;
1556 
1557 template class EhOutputSection<ELF32LE>;
1558 template class EhOutputSection<ELF32BE>;
1559 template class EhOutputSection<ELF64LE>;
1560 template class EhOutputSection<ELF64BE>;
1561 
1562 template class MergeOutputSection<ELF32LE>;
1563 template class MergeOutputSection<ELF32BE>;
1564 template class MergeOutputSection<ELF64LE>;
1565 template class MergeOutputSection<ELF64BE>;
1566 
1567 template class SymbolTableSection<ELF32LE>;
1568 template class SymbolTableSection<ELF32BE>;
1569 template class SymbolTableSection<ELF64LE>;
1570 template class SymbolTableSection<ELF64BE>;
1571 
1572 template class VersionTableSection<ELF32LE>;
1573 template class VersionTableSection<ELF32BE>;
1574 template class VersionTableSection<ELF64LE>;
1575 template class VersionTableSection<ELF64BE>;
1576 
1577 template class VersionNeedSection<ELF32LE>;
1578 template class VersionNeedSection<ELF32BE>;
1579 template class VersionNeedSection<ELF64LE>;
1580 template class VersionNeedSection<ELF64BE>;
1581 
1582 template class VersionDefinitionSection<ELF32LE>;
1583 template class VersionDefinitionSection<ELF32BE>;
1584 template class VersionDefinitionSection<ELF64LE>;
1585 template class VersionDefinitionSection<ELF64BE>;
1586 
1587 template class GdbIndexSection<ELF32LE>;
1588 template class GdbIndexSection<ELF32BE>;
1589 template class GdbIndexSection<ELF64LE>;
1590 template class GdbIndexSection<ELF64BE>;
1591 
1592 template class OutputSectionFactory<ELF32LE>;
1593 template class OutputSectionFactory<ELF32BE>;
1594 template class OutputSectionFactory<ELF64LE>;
1595 template class OutputSectionFactory<ELF64BE>;
1596 }
1597 }
1598