1 //===- InputFiles.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 "InputFiles.h"
11 #include "Error.h"
12 #include "InputSection.h"
13 #include "Symbols.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/IR/LLVMContext.h"
16 #include "llvm/IR/Module.h"
17 #include "llvm/Object/IRObjectFile.h"
18 #include "llvm/Support/raw_ostream.h"
19 
20 using namespace llvm;
21 using namespace llvm::ELF;
22 using namespace llvm::object;
23 using namespace llvm::sys::fs;
24 
25 using namespace lld;
26 using namespace lld::elf;
27 
28 namespace {
29 class ECRAII {
30   std::error_code EC;
31 
32 public:
33   std::error_code &getEC() { return EC; }
34   ~ECRAII() { fatal(EC); }
35 };
36 }
37 
38 template <class ELFT>
39 ELFFileBase<ELFT>::ELFFileBase(Kind K, MemoryBufferRef M)
40     : InputFile(K, M), ELFObj(MB.getBuffer(), ECRAII().getEC()) {}
41 
42 template <class ELFT>
43 ELFKind ELFFileBase<ELFT>::getELFKind() {
44   if (ELFT::TargetEndianness == support::little)
45     return ELFT::Is64Bits ? ELF64LEKind : ELF32LEKind;
46   return ELFT::Is64Bits ? ELF64BEKind : ELF32BEKind;
47 }
48 
49 template <class ELFT>
50 typename ELFFileBase<ELFT>::Elf_Sym_Range
51 ELFFileBase<ELFT>::getSymbolsHelper(bool Local) {
52   if (!Symtab)
53     return Elf_Sym_Range(nullptr, nullptr);
54   Elf_Sym_Range Syms = ELFObj.symbols(Symtab);
55   uint32_t NumSymbols = std::distance(Syms.begin(), Syms.end());
56   uint32_t FirstNonLocal = Symtab->sh_info;
57   if (FirstNonLocal > NumSymbols)
58     fatal("Invalid sh_info in symbol table");
59   if (!Local)
60     return make_range(Syms.begin() + FirstNonLocal, Syms.end());
61   // +1 to skip over dummy symbol.
62   return make_range(Syms.begin() + 1, Syms.begin() + FirstNonLocal);
63 }
64 
65 template <class ELFT>
66 uint32_t ELFFileBase<ELFT>::getSectionIndex(const Elf_Sym &Sym) const {
67   uint32_t I = Sym.st_shndx;
68   if (I == ELF::SHN_XINDEX)
69     return ELFObj.getExtendedSymbolTableIndex(&Sym, Symtab, SymtabSHNDX);
70   if (I >= ELF::SHN_LORESERVE || I == ELF::SHN_ABS)
71     return 0;
72   return I;
73 }
74 
75 template <class ELFT> void ELFFileBase<ELFT>::initStringTable() {
76   if (!Symtab)
77     return;
78   ErrorOr<StringRef> StringTableOrErr = ELFObj.getStringTableForSymtab(*Symtab);
79   fatal(StringTableOrErr);
80   StringTable = *StringTableOrErr;
81 }
82 
83 template <class ELFT>
84 typename ELFFileBase<ELFT>::Elf_Sym_Range
85 ELFFileBase<ELFT>::getNonLocalSymbols() {
86   return getSymbolsHelper(false);
87 }
88 
89 template <class ELFT>
90 elf::ObjectFile<ELFT>::ObjectFile(MemoryBufferRef M)
91     : ELFFileBase<ELFT>(Base::ObjectKind, M) {}
92 
93 template <class ELFT>
94 typename elf::ObjectFile<ELFT>::Elf_Sym_Range
95 elf::ObjectFile<ELFT>::getLocalSymbols() {
96   return this->getSymbolsHelper(true);
97 }
98 
99 template <class ELFT> uint32_t elf::ObjectFile<ELFT>::getMipsGp0() const {
100   if (MipsReginfo)
101     return MipsReginfo->Reginfo->ri_gp_value;
102   return 0;
103 }
104 
105 template <class ELFT>
106 const typename elf::ObjectFile<ELFT>::Elf_Sym *
107 elf::ObjectFile<ELFT>::getLocalSymbol(uintX_t SymIndex) {
108   uint32_t FirstNonLocal = this->Symtab->sh_info;
109   if (SymIndex >= FirstNonLocal)
110     return nullptr;
111   Elf_Sym_Range Syms = this->ELFObj.symbols(this->Symtab);
112   return Syms.begin() + SymIndex;
113 }
114 
115 template <class ELFT>
116 void elf::ObjectFile<ELFT>::parse(DenseSet<StringRef> &ComdatGroups) {
117   // Read section and symbol tables.
118   initializeSections(ComdatGroups);
119   initializeSymbols();
120 }
121 
122 // Sections with SHT_GROUP and comdat bits define comdat section groups.
123 // They are identified and deduplicated by group name. This function
124 // returns a group name.
125 template <class ELFT>
126 StringRef elf::ObjectFile<ELFT>::getShtGroupSignature(const Elf_Shdr &Sec) {
127   const ELFFile<ELFT> &Obj = this->ELFObj;
128   uint32_t SymtabdSectionIndex = Sec.sh_link;
129   ErrorOr<const Elf_Shdr *> SecOrErr = Obj.getSection(SymtabdSectionIndex);
130   fatal(SecOrErr);
131   const Elf_Shdr *SymtabSec = *SecOrErr;
132   uint32_t SymIndex = Sec.sh_info;
133   const Elf_Sym *Sym = Obj.getSymbol(SymtabSec, SymIndex);
134   ErrorOr<StringRef> StringTableOrErr = Obj.getStringTableForSymtab(*SymtabSec);
135   fatal(StringTableOrErr);
136   ErrorOr<StringRef> SignatureOrErr = Sym->getName(*StringTableOrErr);
137   fatal(SignatureOrErr);
138   return *SignatureOrErr;
139 }
140 
141 template <class ELFT>
142 ArrayRef<typename elf::ObjectFile<ELFT>::uint32_X>
143 elf::ObjectFile<ELFT>::getShtGroupEntries(const Elf_Shdr &Sec) {
144   const ELFFile<ELFT> &Obj = this->ELFObj;
145   ErrorOr<ArrayRef<uint32_X>> EntriesOrErr =
146       Obj.template getSectionContentsAsArray<uint32_X>(&Sec);
147   fatal(EntriesOrErr);
148   ArrayRef<uint32_X> Entries = *EntriesOrErr;
149   if (Entries.empty() || Entries[0] != GRP_COMDAT)
150     fatal("Unsupported SHT_GROUP format");
151   return Entries.slice(1);
152 }
153 
154 template <class ELFT>
155 static bool shouldMerge(const typename ELFFile<ELFT>::Elf_Shdr &Sec) {
156   typedef typename ELFFile<ELFT>::uintX_t uintX_t;
157   uintX_t Flags = Sec.sh_flags;
158   if (!(Flags & SHF_MERGE))
159     return false;
160   if (Flags & SHF_WRITE)
161     fatal("Writable SHF_MERGE sections are not supported");
162   uintX_t EntSize = Sec.sh_entsize;
163   if (!EntSize || Sec.sh_size % EntSize)
164     fatal("SHF_MERGE section size must be a multiple of sh_entsize");
165 
166   // Don't try to merge if the aligment is larger than the sh_entsize and this
167   // is not SHF_STRINGS.
168   //
169   // Since this is not a SHF_STRINGS, we would need to pad after every entity.
170   // It would be equivalent for the producer of the .o to just set a larger
171   // sh_entsize.
172   if (Flags & SHF_STRINGS)
173     return true;
174 
175   if (Sec.sh_addralign > EntSize)
176     return false;
177 
178   return true;
179 }
180 
181 template <class ELFT>
182 void elf::ObjectFile<ELFT>::initializeSections(
183     DenseSet<StringRef> &ComdatGroups) {
184   uint64_t Size = this->ELFObj.getNumSections();
185   Sections.resize(Size);
186   unsigned I = -1;
187   const ELFFile<ELFT> &Obj = this->ELFObj;
188   for (const Elf_Shdr &Sec : Obj.sections()) {
189     ++I;
190     if (Sections[I] == InputSection<ELFT>::Discarded)
191       continue;
192 
193     switch (Sec.sh_type) {
194     case SHT_GROUP:
195       Sections[I] = InputSection<ELFT>::Discarded;
196       if (ComdatGroups.insert(getShtGroupSignature(Sec)).second)
197         continue;
198       for (uint32_t SecIndex : getShtGroupEntries(Sec)) {
199         if (SecIndex >= Size)
200           fatal("Invalid section index in group");
201         Sections[SecIndex] = InputSection<ELFT>::Discarded;
202       }
203       break;
204     case SHT_SYMTAB:
205       this->Symtab = &Sec;
206       break;
207     case SHT_SYMTAB_SHNDX: {
208       ErrorOr<ArrayRef<Elf_Word>> ErrorOrTable = Obj.getSHNDXTable(Sec);
209       fatal(ErrorOrTable);
210       this->SymtabSHNDX = *ErrorOrTable;
211       break;
212     }
213     case SHT_STRTAB:
214     case SHT_NULL:
215       break;
216     case SHT_RELA:
217     case SHT_REL: {
218       uint32_t RelocatedSectionIndex = Sec.sh_info;
219       if (RelocatedSectionIndex >= Size)
220         fatal("Invalid relocated section index");
221       InputSectionBase<ELFT> *RelocatedSection =
222           Sections[RelocatedSectionIndex];
223       // Strictly speaking, a relocation section must be included in the
224       // group of the section it relocates. However, LLVM 3.3 and earlier
225       // would fail to do so, so we gracefully handle that case.
226       if (RelocatedSection == InputSection<ELFT>::Discarded)
227         continue;
228       if (!RelocatedSection)
229         fatal("Unsupported relocation reference");
230       if (Config->Relocatable) {
231         // For -r, relocation sections are handled as regular input sections.
232         Sections[I] = new (Alloc) InputSection<ELFT>(this, &Sec);
233       } else if (auto *S = dyn_cast<InputSection<ELFT>>(RelocatedSection)) {
234         S->RelocSections.push_back(&Sec);
235       } else if (auto *S = dyn_cast<EHInputSection<ELFT>>(RelocatedSection)) {
236         if (S->RelocSection)
237           fatal("Multiple relocation sections to .eh_frame are not supported");
238         S->RelocSection = &Sec;
239       } else {
240         fatal("Relocations pointing to SHF_MERGE are not supported");
241       }
242       break;
243     }
244     default:
245       Sections[I] = createInputSection(Sec);
246     }
247   }
248 }
249 
250 template <class ELFT>
251 InputSectionBase<ELFT> *
252 elf::ObjectFile<ELFT>::createInputSection(const Elf_Shdr &Sec) {
253   ErrorOr<StringRef> NameOrErr = this->ELFObj.getSectionName(&Sec);
254   fatal(NameOrErr);
255   StringRef Name = *NameOrErr;
256 
257   // .note.GNU-stack is a marker section to control the presence of
258   // PT_GNU_STACK segment in outputs. Since the presence of the segment
259   // is controlled only by the command line option (-z execstack) in LLD,
260   // .note.GNU-stack is ignored.
261   if (Name == ".note.GNU-stack")
262     return InputSection<ELFT>::Discarded;
263 
264   // A MIPS object file has a special section that contains register
265   // usage info, which needs to be handled by the linker specially.
266   if (Config->EMachine == EM_MIPS && Name == ".reginfo") {
267     MipsReginfo = new (Alloc) MipsReginfoInputSection<ELFT>(this, &Sec);
268     return MipsReginfo;
269   }
270 
271   if (Name == ".eh_frame")
272     return new (EHAlloc.Allocate()) EHInputSection<ELFT>(this, &Sec);
273   if (shouldMerge<ELFT>(Sec))
274     return new (MAlloc.Allocate()) MergeInputSection<ELFT>(this, &Sec);
275   return new (Alloc) InputSection<ELFT>(this, &Sec);
276 }
277 
278 template <class ELFT> void elf::ObjectFile<ELFT>::initializeSymbols() {
279   this->initStringTable();
280   Elf_Sym_Range Syms = this->getNonLocalSymbols();
281   uint32_t NumSymbols = std::distance(Syms.begin(), Syms.end());
282   SymbolBodies.reserve(NumSymbols);
283   for (const Elf_Sym &Sym : Syms)
284     SymbolBodies.push_back(createSymbolBody(&Sym));
285 }
286 
287 template <class ELFT>
288 InputSectionBase<ELFT> *
289 elf::ObjectFile<ELFT>::getSection(const Elf_Sym &Sym) const {
290   uint32_t Index = this->getSectionIndex(Sym);
291   if (Index == 0)
292     return nullptr;
293   if (Index >= Sections.size() || !Sections[Index])
294     fatal("Invalid section index");
295   InputSectionBase<ELFT> *S = Sections[Index];
296   if (S == InputSectionBase<ELFT>::Discarded)
297     return S;
298   return S->Repl;
299 }
300 
301 template <class ELFT>
302 SymbolBody *elf::ObjectFile<ELFT>::createSymbolBody(const Elf_Sym *Sym) {
303   ErrorOr<StringRef> NameOrErr = Sym->getName(this->StringTable);
304   fatal(NameOrErr);
305   StringRef Name = *NameOrErr;
306 
307   switch (Sym->st_shndx) {
308   case SHN_UNDEF:
309     return new (Alloc) UndefinedElf<ELFT>(Name, *Sym);
310   case SHN_COMMON:
311     return new (Alloc) DefinedCommon(Name, Sym->st_size, Sym->st_value,
312                                      Sym->getBinding() == llvm::ELF::STB_WEAK,
313                                      Sym->getVisibility());
314   }
315 
316   switch (Sym->getBinding()) {
317   default:
318     fatal("unexpected binding");
319   case STB_GLOBAL:
320   case STB_WEAK:
321   case STB_GNU_UNIQUE: {
322     InputSectionBase<ELFT> *Sec = getSection(*Sym);
323     if (Sec == InputSection<ELFT>::Discarded)
324       return new (Alloc) UndefinedElf<ELFT>(Name, *Sym);
325     return new (Alloc) DefinedRegular<ELFT>(Name, *Sym, Sec);
326   }
327   }
328 }
329 
330 void ArchiveFile::parse() {
331   ErrorOr<std::unique_ptr<Archive>> FileOrErr = Archive::create(MB);
332   fatal(FileOrErr, "Failed to parse archive");
333   File = std::move(*FileOrErr);
334 
335   // Allocate a buffer for Lazy objects.
336   size_t NumSyms = File->getNumberOfSymbols();
337   LazySymbols.reserve(NumSyms);
338 
339   // Read the symbol table to construct Lazy objects.
340   for (const Archive::Symbol &Sym : File->symbols())
341     LazySymbols.emplace_back(this, Sym);
342 }
343 
344 // Returns a buffer pointing to a member file containing a given symbol.
345 MemoryBufferRef ArchiveFile::getMember(const Archive::Symbol *Sym) {
346   ErrorOr<Archive::Child> COrErr = Sym->getMember();
347   fatal(COrErr, "Could not get the member for symbol " + Sym->getName());
348   const Archive::Child &C = *COrErr;
349 
350   if (!Seen.insert(C.getChildOffset()).second)
351     return MemoryBufferRef();
352 
353   ErrorOr<MemoryBufferRef> RefOrErr = C.getMemoryBufferRef();
354   if (!RefOrErr)
355     fatal(RefOrErr, "Could not get the buffer for the member defining symbol " +
356                         Sym->getName());
357   return *RefOrErr;
358 }
359 
360 template <class ELFT>
361 SharedFile<ELFT>::SharedFile(MemoryBufferRef M)
362     : ELFFileBase<ELFT>(Base::SharedKind, M), AsNeeded(Config->AsNeeded) {}
363 
364 template <class ELFT>
365 const typename ELFFile<ELFT>::Elf_Shdr *
366 SharedFile<ELFT>::getSection(const Elf_Sym &Sym) const {
367   uint32_t Index = this->getSectionIndex(Sym);
368   if (Index == 0)
369     return nullptr;
370   ErrorOr<const Elf_Shdr *> Ret = this->ELFObj.getSection(Index);
371   fatal(Ret);
372   return *Ret;
373 }
374 
375 // Partially parse the shared object file so that we can call
376 // getSoName on this object.
377 template <class ELFT> void SharedFile<ELFT>::parseSoName() {
378   typedef typename ELFFile<ELFT>::Elf_Dyn Elf_Dyn;
379   typedef typename ELFFile<ELFT>::uintX_t uintX_t;
380   const Elf_Shdr *DynamicSec = nullptr;
381 
382   const ELFFile<ELFT> Obj = this->ELFObj;
383   for (const Elf_Shdr &Sec : Obj.sections()) {
384     switch (Sec.sh_type) {
385     default:
386       continue;
387     case SHT_DYNSYM:
388       this->Symtab = &Sec;
389       break;
390     case SHT_DYNAMIC:
391       DynamicSec = &Sec;
392       break;
393     case SHT_SYMTAB_SHNDX: {
394       ErrorOr<ArrayRef<Elf_Word>> ErrorOrTable = Obj.getSHNDXTable(Sec);
395       fatal(ErrorOrTable);
396       this->SymtabSHNDX = *ErrorOrTable;
397       break;
398     }
399     }
400   }
401 
402   this->initStringTable();
403   SoName = this->getName();
404 
405   if (!DynamicSec)
406     return;
407   auto *Begin =
408       reinterpret_cast<const Elf_Dyn *>(Obj.base() + DynamicSec->sh_offset);
409   const Elf_Dyn *End = Begin + DynamicSec->sh_size / sizeof(Elf_Dyn);
410 
411   for (const Elf_Dyn &Dyn : make_range(Begin, End)) {
412     if (Dyn.d_tag == DT_SONAME) {
413       uintX_t Val = Dyn.getVal();
414       if (Val >= this->StringTable.size())
415         fatal("Invalid DT_SONAME entry");
416       SoName = StringRef(this->StringTable.data() + Val);
417       return;
418     }
419   }
420 }
421 
422 // Fully parse the shared object file. This must be called after parseSoName().
423 template <class ELFT> void SharedFile<ELFT>::parseRest() {
424   Elf_Sym_Range Syms = this->getNonLocalSymbols();
425   uint32_t NumSymbols = std::distance(Syms.begin(), Syms.end());
426   SymbolBodies.reserve(NumSymbols);
427   for (const Elf_Sym &Sym : Syms) {
428     ErrorOr<StringRef> NameOrErr = Sym.getName(this->StringTable);
429     fatal(NameOrErr.getError());
430     StringRef Name = *NameOrErr;
431 
432     if (Sym.isUndefined())
433       Undefs.push_back(Name);
434     else
435       SymbolBodies.emplace_back(this, Name, Sym);
436   }
437 }
438 
439 BitcodeFile::BitcodeFile(MemoryBufferRef M) : InputFile(BitcodeKind, M) {}
440 
441 bool BitcodeFile::classof(const InputFile *F) {
442   return F->kind() == BitcodeKind;
443 }
444 
445 void BitcodeFile::parse(DenseSet<StringRef> &ComdatGroups) {
446   LLVMContext Context;
447   ErrorOr<std::unique_ptr<IRObjectFile>> ObjOrErr =
448       IRObjectFile::create(MB, Context);
449   fatal(ObjOrErr);
450   IRObjectFile &Obj = **ObjOrErr;
451   const Module &M = Obj.getModule();
452 
453   DenseSet<const Comdat *> KeptComdats;
454   for (const auto &P : M.getComdatSymbolTable()) {
455     StringRef N = Saver.save(P.first());
456     if (ComdatGroups.insert(N).second)
457       KeptComdats.insert(&P.second);
458   }
459 
460   for (const BasicSymbolRef &Sym : Obj.symbols()) {
461     if (const GlobalValue *GV = Obj.getSymbolGV(Sym.getRawDataRefImpl()))
462       if (const Comdat *C = GV->getComdat())
463         if (!KeptComdats.count(C))
464           continue;
465 
466     SmallString<64> Name;
467     raw_svector_ostream OS(Name);
468     Sym.printName(OS);
469     StringRef NameRef = Saver.save(StringRef(Name));
470     SymbolBody *Body;
471     uint32_t Flags = Sym.getFlags();
472     bool IsWeak = Flags & BasicSymbolRef::SF_Weak;
473     if (Flags & BasicSymbolRef::SF_Undefined)
474       Body = new (Alloc) Undefined(NameRef, IsWeak, STV_DEFAULT, false);
475     else
476       Body = new (Alloc) DefinedBitcode(NameRef, IsWeak);
477     SymbolBodies.push_back(Body);
478   }
479 }
480 
481 template <typename T>
482 static std::unique_ptr<InputFile> createELFFileAux(MemoryBufferRef MB) {
483   std::unique_ptr<T> Ret = llvm::make_unique<T>(MB);
484 
485   if (!Config->FirstElf)
486     Config->FirstElf = Ret.get();
487 
488   if (Config->EKind == ELFNoneKind) {
489     Config->EKind = Ret->getELFKind();
490     Config->EMachine = Ret->getEMachine();
491   }
492 
493   return std::move(Ret);
494 }
495 
496 template <template <class> class T>
497 static std::unique_ptr<InputFile> createELFFile(MemoryBufferRef MB) {
498   std::pair<unsigned char, unsigned char> Type = getElfArchType(MB.getBuffer());
499   if (Type.second != ELF::ELFDATA2LSB && Type.second != ELF::ELFDATA2MSB)
500     fatal("Invalid data encoding: " + MB.getBufferIdentifier());
501 
502   if (Type.first == ELF::ELFCLASS32) {
503     if (Type.second == ELF::ELFDATA2LSB)
504       return createELFFileAux<T<ELF32LE>>(MB);
505     return createELFFileAux<T<ELF32BE>>(MB);
506   }
507   if (Type.first == ELF::ELFCLASS64) {
508     if (Type.second == ELF::ELFDATA2LSB)
509       return createELFFileAux<T<ELF64LE>>(MB);
510     return createELFFileAux<T<ELF64BE>>(MB);
511   }
512   fatal("Invalid file class: " + MB.getBufferIdentifier());
513 }
514 
515 std::unique_ptr<InputFile> elf::createObjectFile(MemoryBufferRef MB,
516                                                  StringRef ArchiveName) {
517   using namespace sys::fs;
518   std::unique_ptr<InputFile> F;
519   if (identify_magic(MB.getBuffer()) == file_magic::bitcode)
520     F.reset(new BitcodeFile(MB));
521   else
522     F = createELFFile<ObjectFile>(MB);
523   F->ArchiveName = ArchiveName;
524   return F;
525 }
526 
527 std::unique_ptr<InputFile> elf::createSharedFile(MemoryBufferRef MB) {
528   return createELFFile<SharedFile>(MB);
529 }
530 
531 template class elf::ELFFileBase<ELF32LE>;
532 template class elf::ELFFileBase<ELF32BE>;
533 template class elf::ELFFileBase<ELF64LE>;
534 template class elf::ELFFileBase<ELF64BE>;
535 
536 template class elf::ObjectFile<ELF32LE>;
537 template class elf::ObjectFile<ELF32BE>;
538 template class elf::ObjectFile<ELF64LE>;
539 template class elf::ObjectFile<ELF64BE>;
540 
541 template class elf::SharedFile<ELF32LE>;
542 template class elf::SharedFile<ELF32BE>;
543 template class elf::SharedFile<ELF64LE>;
544 template class elf::SharedFile<ELF64BE>;
545