1 //===- InputSection.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 "InputSection.h"
11 #include "Config.h"
12 #include "Error.h"
13 #include "InputFiles.h"
14 #include "OutputSections.h"
15 #include "Target.h"
16 
17 #include "llvm/Support/Endian.h"
18 
19 using namespace llvm;
20 using namespace llvm::ELF;
21 using namespace llvm::object;
22 using namespace llvm::support::endian;
23 
24 using namespace lld;
25 using namespace lld::elf;
26 
27 template <class ELFT>
28 InputSectionBase<ELFT>::InputSectionBase(elf::ObjectFile<ELFT> *File,
29                                          const Elf_Shdr *Header,
30                                          Kind SectionKind)
31     : Header(Header), File(File), SectionKind(SectionKind), Repl(this) {
32   // The garbage collector sets sections' Live bits.
33   // If GC is disabled, all sections are considered live by default.
34   Live = !Config->GcSections;
35 
36   // The ELF spec states that a value of 0 means the section has
37   // no alignment constraits.
38   Align = std::max<uintX_t>(Header->sh_addralign, 1);
39 }
40 
41 template <class ELFT> StringRef InputSectionBase<ELFT>::getSectionName() const {
42   return check(File->getObj().getSectionName(this->Header));
43 }
44 
45 template <class ELFT>
46 ArrayRef<uint8_t> InputSectionBase<ELFT>::getSectionData() const {
47   return check(this->File->getObj().getSectionContents(this->Header));
48 }
49 
50 template <class ELFT>
51 typename ELFT::uint InputSectionBase<ELFT>::getOffset(uintX_t Offset) {
52   switch (SectionKind) {
53   case Regular:
54     return cast<InputSection<ELFT>>(this)->OutSecOff + Offset;
55   case EHFrame:
56     return cast<EHInputSection<ELFT>>(this)->getOffset(Offset);
57   case Merge:
58     return cast<MergeInputSection<ELFT>>(this)->getOffset(Offset);
59   case MipsReginfo:
60     // MIPS .reginfo sections are consumed by the linker,
61     // so it should never be copied to output.
62     llvm_unreachable("MIPS .reginfo reached writeTo().");
63   }
64   llvm_unreachable("invalid section kind");
65 }
66 
67 template <class ELFT>
68 typename ELFT::uint InputSectionBase<ELFT>::getOffset(const Elf_Sym &Sym) {
69   return getOffset(Sym.st_value);
70 }
71 
72 // Returns a section that Rel relocation is pointing to.
73 template <class ELFT>
74 InputSectionBase<ELFT> *
75 InputSectionBase<ELFT>::getRelocTarget(const Elf_Rel &Rel) const {
76   // Global symbol
77   uint32_t SymIndex = Rel.getSymbol(Config->Mips64EL);
78   SymbolBody &B = File->getSymbolBody(SymIndex).repl();
79   if (auto *D = dyn_cast<DefinedRegular<ELFT>>(&B))
80     if (D->Section)
81       return D->Section->Repl;
82   return nullptr;
83 }
84 
85 template <class ELFT>
86 InputSectionBase<ELFT> *
87 InputSectionBase<ELFT>::getRelocTarget(const Elf_Rela &Rel) const {
88   return getRelocTarget(reinterpret_cast<const Elf_Rel &>(Rel));
89 }
90 
91 template <class ELFT>
92 InputSection<ELFT>::InputSection(elf::ObjectFile<ELFT> *F,
93                                  const Elf_Shdr *Header)
94     : InputSectionBase<ELFT>(F, Header, Base::Regular) {}
95 
96 template <class ELFT>
97 bool InputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
98   return S->SectionKind == Base::Regular;
99 }
100 
101 template <class ELFT>
102 InputSectionBase<ELFT> *InputSection<ELFT>::getRelocatedSection() {
103   assert(this->Header->sh_type == SHT_RELA || this->Header->sh_type == SHT_REL);
104   ArrayRef<InputSectionBase<ELFT> *> Sections = this->File->getSections();
105   return Sections[this->Header->sh_info];
106 }
107 
108 // This is used for -r. We can't use memcpy to copy relocations because we need
109 // to update symbol table offset and section index for each relocation. So we
110 // copy relocations one by one.
111 template <class ELFT>
112 template <class RelTy>
113 void InputSection<ELFT>::copyRelocations(uint8_t *Buf,
114                                          iterator_range<const RelTy *> Rels) {
115   InputSectionBase<ELFT> *RelocatedSection = getRelocatedSection();
116 
117   for (const RelTy &Rel : Rels) {
118     uint32_t SymIndex = Rel.getSymbol(Config->Mips64EL);
119     uint32_t Type = Rel.getType(Config->Mips64EL);
120     SymbolBody &Body = this->File->getSymbolBody(SymIndex).repl();
121 
122     RelTy *P = reinterpret_cast<RelTy *>(Buf);
123     Buf += sizeof(RelTy);
124 
125     P->r_offset = RelocatedSection->getOffset(Rel.r_offset);
126     P->setSymbolAndType(Body.DynsymIndex, Type, Config->Mips64EL);
127   }
128 }
129 
130 template <class RelTy>
131 static uint32_t getMipsPairType(const RelTy *Rel, const SymbolBody &Sym) {
132   switch (Rel->getType(Config->Mips64EL)) {
133   case R_MIPS_HI16:
134     return R_MIPS_LO16;
135   case R_MIPS_GOT16:
136     return Sym.isLocal() ? R_MIPS_LO16 : R_MIPS_NONE;
137   case R_MIPS_PCHI16:
138     return R_MIPS_PCLO16;
139   case R_MICROMIPS_HI16:
140     return R_MICROMIPS_LO16;
141   default:
142     return R_MIPS_NONE;
143   }
144 }
145 
146 template <class ELFT>
147 template <class RelTy>
148 uint8_t *InputSectionBase<ELFT>::findMipsPairedReloc(uint8_t *Buf,
149                                                      const RelTy *Rel,
150                                                      const RelTy *End) {
151   uint32_t SymIndex = Rel->getSymbol(Config->Mips64EL);
152   SymbolBody &Sym = File->getSymbolBody(SymIndex).repl();
153   uint32_t Type = getMipsPairType(Rel, Sym);
154 
155   // Some MIPS relocations use addend calculated from addend of the relocation
156   // itself and addend of paired relocation. ABI requires to compute such
157   // combined addend in case of REL relocation record format only.
158   // See p. 4-17 at ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
159   if (RelTy::IsRela || Type == R_MIPS_NONE)
160     return nullptr;
161 
162   for (const RelTy *RI = Rel; RI != End; ++RI) {
163     if (RI->getType(Config->Mips64EL) != Type)
164       continue;
165     if (RI->getSymbol(Config->Mips64EL) != SymIndex)
166       continue;
167     uintX_t Offset = getOffset(RI->r_offset);
168     if (Offset == (uintX_t)-1)
169       return nullptr;
170     return Buf + Offset;
171   }
172   return nullptr;
173 }
174 
175 template <class ELFT, class uintX_t>
176 static uintX_t adjustMipsSymVA(uint32_t Type, const elf::ObjectFile<ELFT> &File,
177                                const SymbolBody &Body, uintX_t AddrLoc,
178                                uintX_t SymVA) {
179   if (Type == R_MIPS_HI16 && &Body == Config->MipsGpDisp)
180     return getMipsGpAddr<ELFT>() - AddrLoc;
181   if (Type == R_MIPS_LO16 && &Body == Config->MipsGpDisp)
182     return getMipsGpAddr<ELFT>() - AddrLoc + 4;
183   if (&Body == Config->MipsLocalGp)
184     return getMipsGpAddr<ELFT>();
185   if (Body.isLocal() && (Type == R_MIPS_GPREL16 || Type == R_MIPS_GPREL32))
186     // We need to adjust SymVA value in case of R_MIPS_GPREL16/32
187     // relocations because they use the following expression to calculate
188     // the relocation's result for local symbol: S + A + GP0 - G.
189     return SymVA + File.getMipsGp0();
190   return SymVA;
191 }
192 
193 template <class ELFT, class uintX_t>
194 static uintX_t getMipsGotVA(const SymbolBody &Body, uintX_t SymVA,
195                             uint8_t *BufLoc, uint8_t *PairedLoc) {
196   if (Body.isLocal()) {
197     // If relocation against MIPS local symbol requires GOT entry, this entry
198     // should be initialized by 'page address'. This address is high 16-bits
199     // of sum the symbol's value and the addend. The addend in that case is
200     // calculated using addends from R_MIPS_GOT16 and paired R_MIPS_LO16
201     // relocations.
202     const endianness E = ELFT::TargetEndianness;
203     uint64_t AHL = read32<E>(BufLoc) << 16;
204     if (PairedLoc)
205       AHL += SignExtend64<16>(read32<E>(PairedLoc));
206     return Out<ELFT>::Got->getMipsLocalPageAddr(SymVA + AHL);
207   }
208   if (!Body.isPreemptible())
209     // For non-local symbols GOT entries should contain their full
210     // addresses. But if such symbol cannot be preempted, we do not
211     // have to put them into the "global" part of GOT and use dynamic
212     // linker to determine their actual addresses. That is why we
213     // create GOT entries for them in the "local" part of GOT.
214     return Out<ELFT>::Got->getMipsLocalFullAddr(Body);
215   return Body.getGotVA<ELFT>();
216 }
217 
218 template <class ELFT>
219 template <class RelTy>
220 void InputSectionBase<ELFT>::relocate(uint8_t *Buf, uint8_t *BufEnd,
221                                       iterator_range<const RelTy *> Rels) {
222   size_t Num = Rels.end() - Rels.begin();
223   for (size_t I = 0; I < Num; ++I) {
224     const RelTy &RI = *(Rels.begin() + I);
225     uintX_t Offset = getOffset(RI.r_offset);
226     if (Offset == (uintX_t)-1)
227       continue;
228 
229     uintX_t A = getAddend<ELFT>(RI);
230     uint32_t SymIndex = RI.getSymbol(Config->Mips64EL);
231     uint32_t Type = RI.getType(Config->Mips64EL);
232     uint8_t *BufLoc = Buf + Offset;
233     uintX_t AddrLoc = OutSec->getVA() + Offset;
234 
235     if (Target->pointsToLocalDynamicGotEntry(Type) &&
236         !Target->canRelaxTls(Type, nullptr)) {
237       Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc,
238                           Out<ELFT>::Got->getTlsIndexVA() + A);
239       continue;
240     }
241 
242     SymbolBody &Body = File->getSymbolBody(SymIndex).repl();
243 
244     if (Target->canRelaxTls(Type, &Body)) {
245       uintX_t SymVA;
246       if (Target->needsGot(Type, Body))
247         SymVA = Body.getGotVA<ELFT>();
248       else
249         SymVA = Body.getVA<ELFT>();
250       // By optimizing TLS relocations, it is sometimes needed to skip
251       // relocations that immediately follow TLS relocations. This function
252       // knows how many slots we need to skip.
253       I += Target->relaxTls(BufLoc, BufEnd, Type, AddrLoc, SymVA, Body);
254       continue;
255     }
256 
257     // PPC64 has a special relocation representing the TOC base pointer
258     // that does not have a corresponding symbol.
259     if (Config->EMachine == EM_PPC64 && RI.getType(false) == R_PPC64_TOC) {
260       uintX_t SymVA = getPPC64TocBase() + A;
261       Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc, SymVA, 0);
262       continue;
263     }
264 
265     if (Target->isTlsGlobalDynamicRel(Type) &&
266         !Target->canRelaxTls(Type, &Body)) {
267       Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc,
268                           Out<ELFT>::Got->getGlobalDynAddr(Body) + A);
269       continue;
270     }
271 
272     uintX_t SymVA = Body.getVA<ELFT>(A);
273     uint8_t *PairedLoc = nullptr;
274     if (Config->EMachine == EM_MIPS)
275       PairedLoc = findMipsPairedReloc(Buf, &RI, Rels.end());
276 
277     if (Target->needsPlt(Type, Body)) {
278       SymVA = Body.getPltVA<ELFT>() + A;
279     } else if (Target->needsGot(Type, Body)) {
280       if (Config->EMachine == EM_MIPS)
281         SymVA = getMipsGotVA<ELFT>(Body, SymVA, BufLoc, PairedLoc) + A;
282       else
283         SymVA = Body.getGotVA<ELFT>() + A;
284       if (Body.IsTls)
285         Type = Target->getTlsGotRel(Type);
286     } else if (Target->isSizeRel(Type) && Body.isPreemptible()) {
287       // A SIZE relocation is supposed to set a symbol size, but if a symbol
288       // can be preempted, the size at runtime may be different than link time.
289       // If that's the case, we leave the field alone rather than filling it
290       // with a possibly incorrect value.
291       continue;
292     } else if (Config->EMachine == EM_MIPS) {
293       SymVA = adjustMipsSymVA<ELFT>(Type, *File, Body, AddrLoc, SymVA) + A;
294     } else if (!Target->needsCopyRel<ELFT>(Type, Body) &&
295                Body.isPreemptible()) {
296       continue;
297     }
298     uintX_t Size = Body.getSize<ELFT>();
299     Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc, SymVA, Size + A,
300                         PairedLoc);
301   }
302 }
303 
304 template <class ELFT> void InputSection<ELFT>::writeTo(uint8_t *Buf) {
305   if (this->Header->sh_type == SHT_NOBITS)
306     return;
307   // Copy section contents from source object file to output file.
308   ArrayRef<uint8_t> Data = this->getSectionData();
309   ELFFile<ELFT> &EObj = this->File->getObj();
310 
311   // That happens with -r. In that case we need fix the relocation position and
312   // target. No relocations are applied.
313   if (this->Header->sh_type == SHT_RELA) {
314     this->copyRelocations(Buf + OutSecOff, EObj.relas(this->Header));
315     return;
316   }
317   if (this->Header->sh_type == SHT_REL) {
318     this->copyRelocations(Buf + OutSecOff, EObj.rels(this->Header));
319     return;
320   }
321 
322   memcpy(Buf + OutSecOff, Data.data(), Data.size());
323 
324   uint8_t *BufEnd = Buf + OutSecOff + Data.size();
325   // Iterate over all relocation sections that apply to this section.
326   for (const Elf_Shdr *RelSec : this->RelocSections) {
327     if (RelSec->sh_type == SHT_RELA)
328       this->relocate(Buf, BufEnd, EObj.relas(RelSec));
329     else
330       this->relocate(Buf, BufEnd, EObj.rels(RelSec));
331   }
332 }
333 
334 template <class ELFT>
335 void InputSection<ELFT>::replace(InputSection<ELFT> *Other) {
336   this->Align = std::max(this->Align, Other->Align);
337   Other->Repl = this->Repl;
338   Other->Live = false;
339 }
340 
341 template <class ELFT>
342 SplitInputSection<ELFT>::SplitInputSection(
343     elf::ObjectFile<ELFT> *File, const Elf_Shdr *Header,
344     typename InputSectionBase<ELFT>::Kind SectionKind)
345     : InputSectionBase<ELFT>(File, Header, SectionKind) {}
346 
347 template <class ELFT>
348 EHInputSection<ELFT>::EHInputSection(elf::ObjectFile<ELFT> *F,
349                                      const Elf_Shdr *Header)
350     : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::EHFrame) {
351   // Mark .eh_frame sections as live by default because there are
352   // usually no relocations that point to .eh_frames. Otherwise,
353   // the garbage collector would drop all .eh_frame sections.
354   this->Live = true;
355 }
356 
357 template <class ELFT>
358 bool EHInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
359   return S->SectionKind == InputSectionBase<ELFT>::EHFrame;
360 }
361 
362 template <class ELFT>
363 typename ELFT::uint EHInputSection<ELFT>::getOffset(uintX_t Offset) {
364   // The file crtbeginT.o has relocations pointing to the start of an empty
365   // .eh_frame that is known to be the first in the link. It does that to
366   // identify the start of the output .eh_frame. Handle this special case.
367   if (this->getSectionHdr()->sh_size == 0)
368     return Offset;
369   std::pair<uintX_t, uintX_t> *I = this->getRangeAndSize(Offset).first;
370   uintX_t Base = I->second;
371   if (Base == uintX_t(-1))
372     return -1; // Not in the output
373 
374   uintX_t Addend = Offset - I->first;
375   return Base + Addend;
376 }
377 
378 template <class ELFT>
379 MergeInputSection<ELFT>::MergeInputSection(elf::ObjectFile<ELFT> *F,
380                                            const Elf_Shdr *Header)
381     : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::Merge) {}
382 
383 template <class ELFT>
384 bool MergeInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
385   return S->SectionKind == InputSectionBase<ELFT>::Merge;
386 }
387 
388 template <class ELFT>
389 std::pair<std::pair<typename ELFT::uint, typename ELFT::uint> *,
390           typename ELFT::uint>
391 SplitInputSection<ELFT>::getRangeAndSize(uintX_t Offset) {
392   ArrayRef<uint8_t> D = this->getSectionData();
393   StringRef Data((const char *)D.data(), D.size());
394   uintX_t Size = Data.size();
395   if (Offset >= Size)
396     fatal("entry is past the end of the section");
397 
398   // Find the element this offset points to.
399   auto I = std::upper_bound(
400       Offsets.begin(), Offsets.end(), Offset,
401       [](const uintX_t &A, const std::pair<uintX_t, uintX_t> &B) {
402         return A < B.first;
403       });
404   uintX_t End = I == Offsets.end() ? Data.size() : I->first;
405   --I;
406   return std::make_pair(&*I, End);
407 }
408 
409 template <class ELFT>
410 typename ELFT::uint MergeInputSection<ELFT>::getOffset(uintX_t Offset) {
411   std::pair<std::pair<uintX_t, uintX_t> *, uintX_t> T =
412       this->getRangeAndSize(Offset);
413   std::pair<uintX_t, uintX_t> *I = T.first;
414   uintX_t End = T.second;
415   uintX_t Start = I->first;
416 
417   // Compute the Addend and if the Base is cached, return.
418   uintX_t Addend = Offset - Start;
419   uintX_t &Base = I->second;
420   if (Base != uintX_t(-1))
421     return Base + Addend;
422 
423   // Map the base to the offset in the output section and cache it.
424   ArrayRef<uint8_t> D = this->getSectionData();
425   StringRef Data((const char *)D.data(), D.size());
426   StringRef Entry = Data.substr(Start, End - Start);
427   Base =
428       static_cast<MergeOutputSection<ELFT> *>(this->OutSec)->getOffset(Entry);
429   return Base + Addend;
430 }
431 
432 template <class ELFT>
433 MipsReginfoInputSection<ELFT>::MipsReginfoInputSection(elf::ObjectFile<ELFT> *F,
434                                                        const Elf_Shdr *Hdr)
435     : InputSectionBase<ELFT>(F, Hdr, InputSectionBase<ELFT>::MipsReginfo) {
436   // Initialize this->Reginfo.
437   ArrayRef<uint8_t> D = this->getSectionData();
438   if (D.size() != sizeof(Elf_Mips_RegInfo<ELFT>))
439     fatal("invalid size of .reginfo section");
440   Reginfo = reinterpret_cast<const Elf_Mips_RegInfo<ELFT> *>(D.data());
441 }
442 
443 template <class ELFT>
444 bool MipsReginfoInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
445   return S->SectionKind == InputSectionBase<ELFT>::MipsReginfo;
446 }
447 
448 template class elf::InputSectionBase<ELF32LE>;
449 template class elf::InputSectionBase<ELF32BE>;
450 template class elf::InputSectionBase<ELF64LE>;
451 template class elf::InputSectionBase<ELF64BE>;
452 
453 template class elf::InputSection<ELF32LE>;
454 template class elf::InputSection<ELF32BE>;
455 template class elf::InputSection<ELF64LE>;
456 template class elf::InputSection<ELF64BE>;
457 
458 template class elf::EHInputSection<ELF32LE>;
459 template class elf::EHInputSection<ELF32BE>;
460 template class elf::EHInputSection<ELF64LE>;
461 template class elf::EHInputSection<ELF64BE>;
462 
463 template class elf::MergeInputSection<ELF32LE>;
464 template class elf::MergeInputSection<ELF32BE>;
465 template class elf::MergeInputSection<ELF64LE>;
466 template class elf::MergeInputSection<ELF64BE>;
467 
468 template class elf::MipsReginfoInputSection<ELF32LE>;
469 template class elf::MipsReginfoInputSection<ELF32BE>;
470 template class elf::MipsReginfoInputSection<ELF64LE>;
471 template class elf::MipsReginfoInputSection<ELF64BE>;
472