[ARM] Change ARMAttributeParser::Parse to use support::endianness and simplify
[lldb.git] / lld / ELF / InputFiles.cpp
1 //===- InputFiles.cpp -----------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "InputFiles.h"
10 #include "Driver.h"
11 #include "InputSection.h"
12 #include "LinkerScript.h"
13 #include "SymbolTable.h"
14 #include "Symbols.h"
15 #include "SyntheticSections.h"
16 #include "lld/Common/DWARF.h"
17 #include "lld/Common/ErrorHandler.h"
18 #include "lld/Common/Memory.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/CodeGen/Analysis.h"
21 #include "llvm/IR/LLVMContext.h"
22 #include "llvm/IR/Module.h"
23 #include "llvm/LTO/LTO.h"
24 #include "llvm/MC/StringTableBuilder.h"
25 #include "llvm/Object/ELFObjectFile.h"
26 #include "llvm/Support/ARMAttributeParser.h"
27 #include "llvm/Support/ARMBuildAttributes.h"
28 #include "llvm/Support/Endian.h"
29 #include "llvm/Support/Path.h"
30 #include "llvm/Support/TarWriter.h"
31 #include "llvm/Support/raw_ostream.h"
32
33 using namespace llvm;
34 using namespace llvm::ELF;
35 using namespace llvm::object;
36 using namespace llvm::sys;
37 using namespace llvm::sys::fs;
38 using namespace llvm::support::endian;
39
40 namespace lld {
41 // Returns "<internal>", "foo.a(bar.o)" or "baz.o".
42 std::string toString(const elf::InputFile *f) {
43   if (!f)
44     return "<internal>";
45
46   if (f->toStringCache.empty()) {
47     if (f->archiveName.empty())
48       f->toStringCache = std::string(f->getName());
49     else
50       f->toStringCache = (f->archiveName + "(" + f->getName() + ")").str();
51   }
52   return f->toStringCache;
53 }
54
55 namespace elf {
56 bool InputFile::isInGroup;
57 uint32_t InputFile::nextGroupId;
58 std::vector<BinaryFile *> binaryFiles;
59 std::vector<BitcodeFile *> bitcodeFiles;
60 std::vector<LazyObjFile *> lazyObjFiles;
61 std::vector<InputFile *> objectFiles;
62 std::vector<SharedFile *> sharedFiles;
63
64 std::unique_ptr<TarWriter> tar;
65
66 static ELFKind getELFKind(MemoryBufferRef mb, StringRef archiveName) {
67   unsigned char size;
68   unsigned char endian;
69   std::tie(size, endian) = getElfArchType(mb.getBuffer());
70
71   auto report = [&](StringRef msg) {
72     StringRef filename = mb.getBufferIdentifier();
73     if (archiveName.empty())
74       fatal(filename + ": " + msg);
75     else
76       fatal(archiveName + "(" + filename + "): " + msg);
77   };
78
79   if (!mb.getBuffer().startswith(ElfMagic))
80     report("not an ELF file");
81   if (endian != ELFDATA2LSB && endian != ELFDATA2MSB)
82     report("corrupted ELF file: invalid data encoding");
83   if (size != ELFCLASS32 && size != ELFCLASS64)
84     report("corrupted ELF file: invalid file class");
85
86   size_t bufSize = mb.getBuffer().size();
87   if ((size == ELFCLASS32 && bufSize < sizeof(Elf32_Ehdr)) ||
88       (size == ELFCLASS64 && bufSize < sizeof(Elf64_Ehdr)))
89     report("corrupted ELF file: file is too short");
90
91   if (size == ELFCLASS32)
92     return (endian == ELFDATA2LSB) ? ELF32LEKind : ELF32BEKind;
93   return (endian == ELFDATA2LSB) ? ELF64LEKind : ELF64BEKind;
94 }
95
96 InputFile::InputFile(Kind k, MemoryBufferRef m)
97     : mb(m), groupId(nextGroupId), fileKind(k) {
98   // All files within the same --{start,end}-group get the same group ID.
99   // Otherwise, a new file will get a new group ID.
100   if (!isInGroup)
101     ++nextGroupId;
102 }
103
104 Optional<MemoryBufferRef> readFile(StringRef path) {
105   // The --chroot option changes our virtual root directory.
106   // This is useful when you are dealing with files created by --reproduce.
107   if (!config->chroot.empty() && path.startswith("/"))
108     path = saver.save(config->chroot + path);
109
110   log(path);
111
112   auto mbOrErr = MemoryBuffer::getFile(path, -1, false);
113   if (auto ec = mbOrErr.getError()) {
114     error("cannot open " + path + ": " + ec.message());
115     return None;
116   }
117
118   std::unique_ptr<MemoryBuffer> &mb = *mbOrErr;
119   MemoryBufferRef mbref = mb->getMemBufferRef();
120   make<std::unique_ptr<MemoryBuffer>>(std::move(mb)); // take MB ownership
121
122   if (tar)
123     tar->append(relativeToRoot(path), mbref.getBuffer());
124   return mbref;
125 }
126
127 // All input object files must be for the same architecture
128 // (e.g. it does not make sense to link x86 object files with
129 // MIPS object files.) This function checks for that error.
130 static bool isCompatible(InputFile *file) {
131   if (!file->isElf() && !isa<BitcodeFile>(file))
132     return true;
133
134   if (file->ekind == config->ekind && file->emachine == config->emachine) {
135     if (config->emachine != EM_MIPS)
136       return true;
137     if (isMipsN32Abi(file) == config->mipsN32Abi)
138       return true;
139   }
140
141   if (!config->emulation.empty()) {
142     error(toString(file) + " is incompatible with " + config->emulation);
143     return false;
144   }
145
146   InputFile *existing;
147   if (!objectFiles.empty())
148     existing = objectFiles[0];
149   else if (!sharedFiles.empty())
150     existing = sharedFiles[0];
151   else
152     existing = bitcodeFiles[0];
153
154   error(toString(file) + " is incompatible with " + toString(existing));
155   return false;
156 }
157
158 template <class ELFT> static void doParseFile(InputFile *file) {
159   if (!isCompatible(file))
160     return;
161
162   // Binary file
163   if (auto *f = dyn_cast<BinaryFile>(file)) {
164     binaryFiles.push_back(f);
165     f->parse();
166     return;
167   }
168
169   // .a file
170   if (auto *f = dyn_cast<ArchiveFile>(file)) {
171     f->parse();
172     return;
173   }
174
175   // Lazy object file
176   if (auto *f = dyn_cast<LazyObjFile>(file)) {
177     lazyObjFiles.push_back(f);
178     f->parse<ELFT>();
179     return;
180   }
181
182   if (config->trace)
183     message(toString(file));
184
185   // .so file
186   if (auto *f = dyn_cast<SharedFile>(file)) {
187     f->parse<ELFT>();
188     return;
189   }
190
191   // LLVM bitcode file
192   if (auto *f = dyn_cast<BitcodeFile>(file)) {
193     bitcodeFiles.push_back(f);
194     f->parse<ELFT>();
195     return;
196   }
197
198   // Regular object file
199   objectFiles.push_back(file);
200   cast<ObjFile<ELFT>>(file)->parse();
201 }
202
203 // Add symbols in File to the symbol table.
204 void parseFile(InputFile *file) {
205   switch (config->ekind) {
206   case ELF32LEKind:
207     doParseFile<ELF32LE>(file);
208     return;
209   case ELF32BEKind:
210     doParseFile<ELF32BE>(file);
211     return;
212   case ELF64LEKind:
213     doParseFile<ELF64LE>(file);
214     return;
215   case ELF64BEKind:
216     doParseFile<ELF64BE>(file);
217     return;
218   default:
219     llvm_unreachable("unknown ELFT");
220   }
221 }
222
223 // Concatenates arguments to construct a string representing an error location.
224 static std::string createFileLineMsg(StringRef path, unsigned line) {
225   std::string filename = std::string(path::filename(path));
226   std::string lineno = ":" + std::to_string(line);
227   if (filename == path)
228     return filename + lineno;
229   return filename + lineno + " (" + path.str() + lineno + ")";
230 }
231
232 template <class ELFT>
233 static std::string getSrcMsgAux(ObjFile<ELFT> &file, const Symbol &sym,
234                                 InputSectionBase &sec, uint64_t offset) {
235   // In DWARF, functions and variables are stored to different places.
236   // First, lookup a function for a given offset.
237   if (Optional<DILineInfo> info = file.getDILineInfo(&sec, offset))
238     return createFileLineMsg(info->FileName, info->Line);
239
240   // If it failed, lookup again as a variable.
241   if (Optional<std::pair<std::string, unsigned>> fileLine =
242           file.getVariableLoc(sym.getName()))
243     return createFileLineMsg(fileLine->first, fileLine->second);
244
245   // File.sourceFile contains STT_FILE symbol, and that is a last resort.
246   return std::string(file.sourceFile);
247 }
248
249 std::string InputFile::getSrcMsg(const Symbol &sym, InputSectionBase &sec,
250                                  uint64_t offset) {
251   if (kind() != ObjKind)
252     return "";
253   switch (config->ekind) {
254   default:
255     llvm_unreachable("Invalid kind");
256   case ELF32LEKind:
257     return getSrcMsgAux(cast<ObjFile<ELF32LE>>(*this), sym, sec, offset);
258   case ELF32BEKind:
259     return getSrcMsgAux(cast<ObjFile<ELF32BE>>(*this), sym, sec, offset);
260   case ELF64LEKind:
261     return getSrcMsgAux(cast<ObjFile<ELF64LE>>(*this), sym, sec, offset);
262   case ELF64BEKind:
263     return getSrcMsgAux(cast<ObjFile<ELF64BE>>(*this), sym, sec, offset);
264   }
265 }
266
267 template <class ELFT> void ObjFile<ELFT>::initializeDwarf() {
268   dwarf = make<DWARFCache>(std::make_unique<DWARFContext>(
269       std::make_unique<LLDDwarfObj<ELFT>>(this)));
270 }
271
272 // Returns the pair of file name and line number describing location of data
273 // object (variable, array, etc) definition.
274 template <class ELFT>
275 Optional<std::pair<std::string, unsigned>>
276 ObjFile<ELFT>::getVariableLoc(StringRef name) {
277   llvm::call_once(initDwarfLine, [this]() { initializeDwarf(); });
278
279   return dwarf->getVariableLoc(name);
280 }
281
282 // Returns source line information for a given offset
283 // using DWARF debug info.
284 template <class ELFT>
285 Optional<DILineInfo> ObjFile<ELFT>::getDILineInfo(InputSectionBase *s,
286                                                   uint64_t offset) {
287   llvm::call_once(initDwarfLine, [this]() { initializeDwarf(); });
288
289   // Detect SectionIndex for specified section.
290   uint64_t sectionIndex = object::SectionedAddress::UndefSection;
291   ArrayRef<InputSectionBase *> sections = s->file->getSections();
292   for (uint64_t curIndex = 0; curIndex < sections.size(); ++curIndex) {
293     if (s == sections[curIndex]) {
294       sectionIndex = curIndex;
295       break;
296     }
297   }
298
299   // Use fake address calculated by adding section file offset and offset in
300   // section. See comments for ObjectInfo class.
301   return dwarf->getDILineInfo(s->getOffsetInFile() + offset, sectionIndex);
302 }
303
304 ELFFileBase::ELFFileBase(Kind k, MemoryBufferRef mb) : InputFile(k, mb) {
305   ekind = getELFKind(mb, "");
306
307   switch (ekind) {
308   case ELF32LEKind:
309     init<ELF32LE>();
310     break;
311   case ELF32BEKind:
312     init<ELF32BE>();
313     break;
314   case ELF64LEKind:
315     init<ELF64LE>();
316     break;
317   case ELF64BEKind:
318     init<ELF64BE>();
319     break;
320   default:
321     llvm_unreachable("getELFKind");
322   }
323 }
324
325 template <typename Elf_Shdr>
326 static const Elf_Shdr *findSection(ArrayRef<Elf_Shdr> sections, uint32_t type) {
327   for (const Elf_Shdr &sec : sections)
328     if (sec.sh_type == type)
329       return &sec;
330   return nullptr;
331 }
332
333 template <class ELFT> void ELFFileBase::init() {
334   using Elf_Shdr = typename ELFT::Shdr;
335   using Elf_Sym = typename ELFT::Sym;
336
337   // Initialize trivial attributes.
338   const ELFFile<ELFT> &obj = getObj<ELFT>();
339   emachine = obj.getHeader()->e_machine;
340   osabi = obj.getHeader()->e_ident[llvm::ELF::EI_OSABI];
341   abiVersion = obj.getHeader()->e_ident[llvm::ELF::EI_ABIVERSION];
342
343   ArrayRef<Elf_Shdr> sections = CHECK(obj.sections(), this);
344
345   // Find a symbol table.
346   bool isDSO =
347       (identify_magic(mb.getBuffer()) == file_magic::elf_shared_object);
348   const Elf_Shdr *symtabSec =
349       findSection(sections, isDSO ? SHT_DYNSYM : SHT_SYMTAB);
350
351   if (!symtabSec)
352     return;
353
354   // Initialize members corresponding to a symbol table.
355   firstGlobal = symtabSec->sh_info;
356
357   ArrayRef<Elf_Sym> eSyms = CHECK(obj.symbols(symtabSec), this);
358   if (firstGlobal == 0 || firstGlobal > eSyms.size())
359     fatal(toString(this) + ": invalid sh_info in symbol table");
360
361   elfSyms = reinterpret_cast<const void *>(eSyms.data());
362   numELFSyms = eSyms.size();
363   stringTable = CHECK(obj.getStringTableForSymtab(*symtabSec, sections), this);
364 }
365
366 template <class ELFT>
367 uint32_t ObjFile<ELFT>::getSectionIndex(const Elf_Sym &sym) const {
368   return CHECK(
369       this->getObj().getSectionIndex(&sym, getELFSyms<ELFT>(), shndxTable),
370       this);
371 }
372
373 template <class ELFT> ArrayRef<Symbol *> ObjFile<ELFT>::getLocalSymbols() {
374   if (this->symbols.empty())
375     return {};
376   return makeArrayRef(this->symbols).slice(1, this->firstGlobal - 1);
377 }
378
379 template <class ELFT> ArrayRef<Symbol *> ObjFile<ELFT>::getGlobalSymbols() {
380   return makeArrayRef(this->symbols).slice(this->firstGlobal);
381 }
382
383 template <class ELFT> void ObjFile<ELFT>::parse(bool ignoreComdats) {
384   // Read a section table. justSymbols is usually false.
385   if (this->justSymbols)
386     initializeJustSymbols();
387   else
388     initializeSections(ignoreComdats);
389
390   // Read a symbol table.
391   initializeSymbols();
392 }
393
394 // Sections with SHT_GROUP and comdat bits define comdat section groups.
395 // They are identified and deduplicated by group name. This function
396 // returns a group name.
397 template <class ELFT>
398 StringRef ObjFile<ELFT>::getShtGroupSignature(ArrayRef<Elf_Shdr> sections,
399                                               const Elf_Shdr &sec) {
400   typename ELFT::SymRange symbols = this->getELFSyms<ELFT>();
401   if (sec.sh_info >= symbols.size())
402     fatal(toString(this) + ": invalid symbol index");
403   const typename ELFT::Sym &sym = symbols[sec.sh_info];
404   StringRef signature = CHECK(sym.getName(this->stringTable), this);
405
406   // As a special case, if a symbol is a section symbol and has no name,
407   // we use a section name as a signature.
408   //
409   // Such SHT_GROUP sections are invalid from the perspective of the ELF
410   // standard, but GNU gold 1.14 (the newest version as of July 2017) or
411   // older produce such sections as outputs for the -r option, so we need
412   // a bug-compatibility.
413   if (signature.empty() && sym.getType() == STT_SECTION)
414     return getSectionName(sec);
415   return signature;
416 }
417
418 template <class ELFT>
419 bool ObjFile<ELFT>::shouldMerge(const Elf_Shdr &sec, StringRef name) {
420   // On a regular link we don't merge sections if -O0 (default is -O1). This
421   // sometimes makes the linker significantly faster, although the output will
422   // be bigger.
423   //
424   // Doing the same for -r would create a problem as it would combine sections
425   // with different sh_entsize. One option would be to just copy every SHF_MERGE
426   // section as is to the output. While this would produce a valid ELF file with
427   // usable SHF_MERGE sections, tools like (llvm-)?dwarfdump get confused when
428   // they see two .debug_str. We could have separate logic for combining
429   // SHF_MERGE sections based both on their name and sh_entsize, but that seems
430   // to be more trouble than it is worth. Instead, we just use the regular (-O1)
431   // logic for -r.
432   if (config->optimize == 0 && !config->relocatable)
433     return false;
434
435   // A mergeable section with size 0 is useless because they don't have
436   // any data to merge. A mergeable string section with size 0 can be
437   // argued as invalid because it doesn't end with a null character.
438   // We'll avoid a mess by handling them as if they were non-mergeable.
439   if (sec.sh_size == 0)
440     return false;
441
442   // Check for sh_entsize. The ELF spec is not clear about the zero
443   // sh_entsize. It says that "the member [sh_entsize] contains 0 if
444   // the section does not hold a table of fixed-size entries". We know
445   // that Rust 1.13 produces a string mergeable section with a zero
446   // sh_entsize. Here we just accept it rather than being picky about it.
447   uint64_t entSize = sec.sh_entsize;
448   if (entSize == 0)
449     return false;
450   if (sec.sh_size % entSize)
451     fatal(toString(this) + ":(" + name + "): SHF_MERGE section size (" +
452           Twine(sec.sh_size) + ") must be a multiple of sh_entsize (" +
453           Twine(entSize) + ")");
454
455   uint64_t flags = sec.sh_flags;
456   if (!(flags & SHF_MERGE))
457     return false;
458   if (flags & SHF_WRITE)
459     fatal(toString(this) + ":(" + name +
460           "): writable SHF_MERGE section is not supported");
461
462   return true;
463 }
464
465 // This is for --just-symbols.
466 //
467 // --just-symbols is a very minor feature that allows you to link your
468 // output against other existing program, so that if you load both your
469 // program and the other program into memory, your output can refer the
470 // other program's symbols.
471 //
472 // When the option is given, we link "just symbols". The section table is
473 // initialized with null pointers.
474 template <class ELFT> void ObjFile<ELFT>::initializeJustSymbols() {
475   ArrayRef<Elf_Shdr> sections = CHECK(this->getObj().sections(), this);
476   this->sections.resize(sections.size());
477 }
478
479 // An ELF object file may contain a `.deplibs` section. If it exists, the
480 // section contains a list of library specifiers such as `m` for libm. This
481 // function resolves a given name by finding the first matching library checking
482 // the various ways that a library can be specified to LLD. This ELF extension
483 // is a form of autolinking and is called `dependent libraries`. It is currently
484 // unique to LLVM and lld.
485 static void addDependentLibrary(StringRef specifier, const InputFile *f) {
486   if (!config->dependentLibraries)
487     return;
488   if (fs::exists(specifier))
489     driver->addFile(specifier, /*withLOption=*/false);
490   else if (Optional<std::string> s = findFromSearchPaths(specifier))
491     driver->addFile(*s, /*withLOption=*/true);
492   else if (Optional<std::string> s = searchLibraryBaseName(specifier))
493     driver->addFile(*s, /*withLOption=*/true);
494   else
495     error(toString(f) +
496           ": unable to find library from dependent library specifier: " +
497           specifier);
498 }
499
500 // Record the membership of a section group so that in the garbage collection
501 // pass, section group members are kept or discarded as a unit.
502 template <class ELFT>
503 static void handleSectionGroup(ArrayRef<InputSectionBase *> sections,
504                                ArrayRef<typename ELFT::Word> entries) {
505   bool hasAlloc = false;
506   for (uint32_t index : entries.slice(1)) {
507     if (index >= sections.size())
508       return;
509     if (InputSectionBase *s = sections[index])
510       if (s != &InputSection::discarded && s->flags & SHF_ALLOC)
511         hasAlloc = true;
512   }
513
514   // If any member has the SHF_ALLOC flag, the whole group is subject to garbage
515   // collection. See the comment in markLive(). This rule retains .debug_types
516   // and .rela.debug_types.
517   if (!hasAlloc)
518     return;
519
520   // Connect the members in a circular doubly-linked list via
521   // nextInSectionGroup.
522   InputSectionBase *head;
523   InputSectionBase *prev = nullptr;
524   for (uint32_t index : entries.slice(1)) {
525     InputSectionBase *s = sections[index];
526     if (!s || s == &InputSection::discarded)
527       continue;
528     if (prev)
529       prev->nextInSectionGroup = s;
530     else
531       head = s;
532     prev = s;
533   }
534   if (prev)
535     prev->nextInSectionGroup = head;
536 }
537
538 template <class ELFT>
539 void ObjFile<ELFT>::initializeSections(bool ignoreComdats) {
540   const ELFFile<ELFT> &obj = this->getObj();
541
542   ArrayRef<Elf_Shdr> objSections = CHECK(obj.sections(), this);
543   uint64_t size = objSections.size();
544   this->sections.resize(size);
545   this->sectionStringTable =
546       CHECK(obj.getSectionStringTable(objSections), this);
547
548   std::vector<ArrayRef<Elf_Word>> selectedGroups;
549
550   for (size_t i = 0, e = objSections.size(); i < e; ++i) {
551     if (this->sections[i] == &InputSection::discarded)
552       continue;
553     const Elf_Shdr &sec = objSections[i];
554
555     if (sec.sh_type == ELF::SHT_LLVM_CALL_GRAPH_PROFILE)
556       cgProfile =
557           check(obj.template getSectionContentsAsArray<Elf_CGProfile>(&sec));
558
559     // SHF_EXCLUDE'ed sections are discarded by the linker. However,
560     // if -r is given, we'll let the final link discard such sections.
561     // This is compatible with GNU.
562     if ((sec.sh_flags & SHF_EXCLUDE) && !config->relocatable) {
563       if (sec.sh_type == SHT_LLVM_ADDRSIG) {
564         // We ignore the address-significance table if we know that the object
565         // file was created by objcopy or ld -r. This is because these tools
566         // will reorder the symbols in the symbol table, invalidating the data
567         // in the address-significance table, which refers to symbols by index.
568         if (sec.sh_link != 0)
569           this->addrsigSec = &sec;
570         else if (config->icf == ICFLevel::Safe)
571           warn(toString(this) + ": --icf=safe is incompatible with object "
572                                 "files created using objcopy or ld -r");
573       }
574       this->sections[i] = &InputSection::discarded;
575       continue;
576     }
577
578     switch (sec.sh_type) {
579     case SHT_GROUP: {
580       // De-duplicate section groups by their signatures.
581       StringRef signature = getShtGroupSignature(objSections, sec);
582       this->sections[i] = &InputSection::discarded;
583
584
585       ArrayRef<Elf_Word> entries =
586           CHECK(obj.template getSectionContentsAsArray<Elf_Word>(&sec), this);
587       if (entries.empty())
588         fatal(toString(this) + ": empty SHT_GROUP");
589
590       // The first word of a SHT_GROUP section contains flags. Currently,
591       // the standard defines only "GRP_COMDAT" flag for the COMDAT group.
592       // An group with the empty flag doesn't define anything; such sections
593       // are just skipped.
594       if (entries[0] == 0)
595         continue;
596
597       if (entries[0] != GRP_COMDAT)
598         fatal(toString(this) + ": unsupported SHT_GROUP format");
599
600       bool isNew =
601           ignoreComdats ||
602           symtab->comdatGroups.try_emplace(CachedHashStringRef(signature), this)
603               .second;
604       if (isNew) {
605         if (config->relocatable)
606           this->sections[i] = createInputSection(sec);
607         selectedGroups.push_back(entries);
608         continue;
609       }
610
611       // Otherwise, discard group members.
612       for (uint32_t secIndex : entries.slice(1)) {
613         if (secIndex >= size)
614           fatal(toString(this) +
615                 ": invalid section index in group: " + Twine(secIndex));
616         this->sections[secIndex] = &InputSection::discarded;
617       }
618       break;
619     }
620     case SHT_SYMTAB_SHNDX:
621       shndxTable = CHECK(obj.getSHNDXTable(sec, objSections), this);
622       break;
623     case SHT_SYMTAB:
624     case SHT_STRTAB:
625     case SHT_NULL:
626       break;
627     default:
628       this->sections[i] = createInputSection(sec);
629     }
630   }
631
632   // This block handles SHF_LINK_ORDER.
633   for (size_t i = 0, e = objSections.size(); i < e; ++i) {
634     if (this->sections[i] == &InputSection::discarded)
635       continue;
636     const Elf_Shdr &sec = objSections[i];
637     if (!(sec.sh_flags & SHF_LINK_ORDER))
638       continue;
639
640     // .ARM.exidx sections have a reverse dependency on the InputSection they
641     // have a SHF_LINK_ORDER dependency, this is identified by the sh_link.
642     InputSectionBase *linkSec = nullptr;
643     if (sec.sh_link < this->sections.size())
644       linkSec = this->sections[sec.sh_link];
645     if (!linkSec)
646       fatal(toString(this) + ": invalid sh_link index: " + Twine(sec.sh_link));
647
648     InputSection *isec = cast<InputSection>(this->sections[i]);
649     linkSec->dependentSections.push_back(isec);
650     if (!isa<InputSection>(linkSec))
651       error("a section " + isec->name +
652             " with SHF_LINK_ORDER should not refer a non-regular section: " +
653             toString(linkSec));
654   }
655
656   for (ArrayRef<Elf_Word> entries : selectedGroups)
657     handleSectionGroup<ELFT>(this->sections, entries);
658 }
659
660 // For ARM only, to set the EF_ARM_ABI_FLOAT_SOFT or EF_ARM_ABI_FLOAT_HARD
661 // flag in the ELF Header we need to look at Tag_ABI_VFP_args to find out how
662 // the input objects have been compiled.
663 static void updateARMVFPArgs(const ARMAttributeParser &attributes,
664                              const InputFile *f) {
665   if (!attributes.hasAttribute(ARMBuildAttrs::ABI_VFP_args))
666     // If an ABI tag isn't present then it is implicitly given the value of 0
667     // which maps to ARMBuildAttrs::BaseAAPCS. However many assembler files,
668     // including some in glibc that don't use FP args (and should have value 3)
669     // don't have the attribute so we do not consider an implicit value of 0
670     // as a clash.
671     return;
672
673   unsigned vfpArgs = attributes.getAttributeValue(ARMBuildAttrs::ABI_VFP_args);
674   ARMVFPArgKind arg;
675   switch (vfpArgs) {
676   case ARMBuildAttrs::BaseAAPCS:
677     arg = ARMVFPArgKind::Base;
678     break;
679   case ARMBuildAttrs::HardFPAAPCS:
680     arg = ARMVFPArgKind::VFP;
681     break;
682   case ARMBuildAttrs::ToolChainFPPCS:
683     // Tool chain specific convention that conforms to neither AAPCS variant.
684     arg = ARMVFPArgKind::ToolChain;
685     break;
686   case ARMBuildAttrs::CompatibleFPAAPCS:
687     // Object compatible with all conventions.
688     return;
689   default:
690     error(toString(f) + ": unknown Tag_ABI_VFP_args value: " + Twine(vfpArgs));
691     return;
692   }
693   // Follow ld.bfd and error if there is a mix of calling conventions.
694   if (config->armVFPArgs != arg && config->armVFPArgs != ARMVFPArgKind::Default)
695     error(toString(f) + ": incompatible Tag_ABI_VFP_args");
696   else
697     config->armVFPArgs = arg;
698 }
699
700 // The ARM support in lld makes some use of instructions that are not available
701 // on all ARM architectures. Namely:
702 // - Use of BLX instruction for interworking between ARM and Thumb state.
703 // - Use of the extended Thumb branch encoding in relocation.
704 // - Use of the MOVT/MOVW instructions in Thumb Thunks.
705 // The ARM Attributes section contains information about the architecture chosen
706 // at compile time. We follow the convention that if at least one input object
707 // is compiled with an architecture that supports these features then lld is
708 // permitted to use them.
709 static void updateSupportedARMFeatures(const ARMAttributeParser &attributes) {
710   if (!attributes.hasAttribute(ARMBuildAttrs::CPU_arch))
711     return;
712   auto arch = attributes.getAttributeValue(ARMBuildAttrs::CPU_arch);
713   switch (arch) {
714   case ARMBuildAttrs::Pre_v4:
715   case ARMBuildAttrs::v4:
716   case ARMBuildAttrs::v4T:
717     // Architectures prior to v5 do not support BLX instruction
718     break;
719   case ARMBuildAttrs::v5T:
720   case ARMBuildAttrs::v5TE:
721   case ARMBuildAttrs::v5TEJ:
722   case ARMBuildAttrs::v6:
723   case ARMBuildAttrs::v6KZ:
724   case ARMBuildAttrs::v6K:
725     config->armHasBlx = true;
726     // Architectures used in pre-Cortex processors do not support
727     // The J1 = 1 J2 = 1 Thumb branch range extension, with the exception
728     // of Architecture v6T2 (arm1156t2-s and arm1156t2f-s) that do.
729     break;
730   default:
731     // All other Architectures have BLX and extended branch encoding
732     config->armHasBlx = true;
733     config->armJ1J2BranchEncoding = true;
734     if (arch != ARMBuildAttrs::v6_M && arch != ARMBuildAttrs::v6S_M)
735       // All Architectures used in Cortex processors with the exception
736       // of v6-M and v6S-M have the MOVT and MOVW instructions.
737       config->armHasMovtMovw = true;
738     break;
739   }
740 }
741
742 // If a source file is compiled with x86 hardware-assisted call flow control
743 // enabled, the generated object file contains feature flags indicating that
744 // fact. This function reads the feature flags and returns it.
745 //
746 // Essentially we want to read a single 32-bit value in this function, but this
747 // function is rather complicated because the value is buried deep inside a
748 // .note.gnu.property section.
749 //
750 // The section consists of one or more NOTE records. Each NOTE record consists
751 // of zero or more type-length-value fields. We want to find a field of a
752 // certain type. It seems a bit too much to just store a 32-bit value, perhaps
753 // the ABI is unnecessarily complicated.
754 template <class ELFT>
755 static uint32_t readAndFeatures(ObjFile<ELFT> *obj, ArrayRef<uint8_t> data) {
756   using Elf_Nhdr = typename ELFT::Nhdr;
757   using Elf_Note = typename ELFT::Note;
758
759   uint32_t featuresSet = 0;
760   while (!data.empty()) {
761     // Read one NOTE record.
762     if (data.size() < sizeof(Elf_Nhdr))
763       fatal(toString(obj) + ": .note.gnu.property: section too short");
764
765     auto *nhdr = reinterpret_cast<const Elf_Nhdr *>(data.data());
766     if (data.size() < nhdr->getSize())
767       fatal(toString(obj) + ": .note.gnu.property: section too short");
768
769     Elf_Note note(*nhdr);
770     if (nhdr->n_type != NT_GNU_PROPERTY_TYPE_0 || note.getName() != "GNU") {
771       data = data.slice(nhdr->getSize());
772       continue;
773     }
774
775     uint32_t featureAndType = config->emachine == EM_AARCH64
776                                   ? GNU_PROPERTY_AARCH64_FEATURE_1_AND
777                                   : GNU_PROPERTY_X86_FEATURE_1_AND;
778
779     // Read a body of a NOTE record, which consists of type-length-value fields.
780     ArrayRef<uint8_t> desc = note.getDesc();
781     while (!desc.empty()) {
782       if (desc.size() < 8)
783         fatal(toString(obj) + ": .note.gnu.property: section too short");
784
785       uint32_t type = read32le(desc.data());
786       uint32_t size = read32le(desc.data() + 4);
787
788       if (type == featureAndType) {
789         // We found a FEATURE_1_AND field. There may be more than one of these
790         // in a .note.gnu.property section, for a relocatable object we
791         // accumulate the bits set.
792         featuresSet |= read32le(desc.data() + 8);
793       }
794
795       // On 64-bit, a payload may be followed by a 4-byte padding to make its
796       // size a multiple of 8.
797       if (ELFT::Is64Bits)
798         size = alignTo(size, 8);
799
800       desc = desc.slice(size + 8); // +8 for Type and Size
801     }
802
803     // Go to next NOTE record to look for more FEATURE_1_AND descriptions.
804     data = data.slice(nhdr->getSize());
805   }
806
807   return featuresSet;
808 }
809
810 template <class ELFT>
811 InputSectionBase *ObjFile<ELFT>::getRelocTarget(const Elf_Shdr &sec) {
812   uint32_t idx = sec.sh_info;
813   if (idx >= this->sections.size())
814     fatal(toString(this) + ": invalid relocated section index: " + Twine(idx));
815   InputSectionBase *target = this->sections[idx];
816
817   // Strictly speaking, a relocation section must be included in the
818   // group of the section it relocates. However, LLVM 3.3 and earlier
819   // would fail to do so, so we gracefully handle that case.
820   if (target == &InputSection::discarded)
821     return nullptr;
822
823   if (!target)
824     fatal(toString(this) + ": unsupported relocation reference");
825   return target;
826 }
827
828 // Create a regular InputSection class that has the same contents
829 // as a given section.
830 static InputSection *toRegularSection(MergeInputSection *sec) {
831   return make<InputSection>(sec->file, sec->flags, sec->type, sec->alignment,
832                             sec->data(), sec->name);
833 }
834
835 template <class ELFT>
836 InputSectionBase *ObjFile<ELFT>::createInputSection(const Elf_Shdr &sec) {
837   StringRef name = getSectionName(sec);
838
839   switch (sec.sh_type) {
840   case SHT_ARM_ATTRIBUTES: {
841     if (config->emachine != EM_ARM)
842       break;
843     ARMAttributeParser attributes;
844     ArrayRef<uint8_t> contents = check(this->getObj().getSectionContents(&sec));
845     attributes.parse(contents, config->ekind == ELF32LEKind ? support::little
846                                                             : support::big);
847     updateSupportedARMFeatures(attributes);
848     updateARMVFPArgs(attributes, this);
849
850     // FIXME: Retain the first attribute section we see. The eglibc ARM
851     // dynamic loaders require the presence of an attribute section for dlopen
852     // to work. In a full implementation we would merge all attribute sections.
853     if (in.armAttributes == nullptr) {
854       in.armAttributes = make<InputSection>(*this, sec, name);
855       return in.armAttributes;
856     }
857     return &InputSection::discarded;
858   }
859   case SHT_LLVM_DEPENDENT_LIBRARIES: {
860     if (config->relocatable)
861       break;
862     ArrayRef<char> data =
863         CHECK(this->getObj().template getSectionContentsAsArray<char>(&sec), this);
864     if (!data.empty() && data.back() != '\0') {
865       error(toString(this) +
866             ": corrupted dependent libraries section (unterminated string): " +
867             name);
868       return &InputSection::discarded;
869     }
870     for (const char *d = data.begin(), *e = data.end(); d < e;) {
871       StringRef s(d);
872       addDependentLibrary(s, this);
873       d += s.size() + 1;
874     }
875     return &InputSection::discarded;
876   }
877   case SHT_RELA:
878   case SHT_REL: {
879     // Find a relocation target section and associate this section with that.
880     // Target may have been discarded if it is in a different section group
881     // and the group is discarded, even though it's a violation of the
882     // spec. We handle that situation gracefully by discarding dangling
883     // relocation sections.
884     InputSectionBase *target = getRelocTarget(sec);
885     if (!target)
886       return nullptr;
887
888     // ELF spec allows mergeable sections with relocations, but they are
889     // rare, and it is in practice hard to merge such sections by contents,
890     // because applying relocations at end of linking changes section
891     // contents. So, we simply handle such sections as non-mergeable ones.
892     // Degrading like this is acceptable because section merging is optional.
893     if (auto *ms = dyn_cast<MergeInputSection>(target)) {
894       target = toRegularSection(ms);
895       this->sections[sec.sh_info] = target;
896     }
897
898     // This section contains relocation information.
899     // If -r is given, we do not interpret or apply relocation
900     // but just copy relocation sections to output.
901     if (config->relocatable) {
902       InputSection *relocSec = make<InputSection>(*this, sec, name);
903       // We want to add a dependency to target, similar like we do for
904       // -emit-relocs below. This is useful for the case when linker script
905       // contains the "/DISCARD/". It is perhaps uncommon to use a script with
906       // -r, but we faced it in the Linux kernel and have to handle such case
907       // and not to crash.
908       target->dependentSections.push_back(relocSec);
909       return relocSec;
910     }
911
912     if (target->firstRelocation)
913       fatal(toString(this) +
914             ": multiple relocation sections to one section are not supported");
915
916     if (sec.sh_type == SHT_RELA) {
917       ArrayRef<Elf_Rela> rels = CHECK(getObj().relas(&sec), this);
918       target->firstRelocation = rels.begin();
919       target->numRelocations = rels.size();
920       target->areRelocsRela = true;
921     } else {
922       ArrayRef<Elf_Rel> rels = CHECK(getObj().rels(&sec), this);
923       target->firstRelocation = rels.begin();
924       target->numRelocations = rels.size();
925       target->areRelocsRela = false;
926     }
927     assert(isUInt<31>(target->numRelocations));
928
929     // Relocation sections processed by the linker are usually removed
930     // from the output, so returning `nullptr` for the normal case.
931     // However, if -emit-relocs is given, we need to leave them in the output.
932     // (Some post link analysis tools need this information.)
933     if (config->emitRelocs) {
934       InputSection *relocSec = make<InputSection>(*this, sec, name);
935       // We will not emit relocation section if target was discarded.
936       target->dependentSections.push_back(relocSec);
937       return relocSec;
938     }
939     return nullptr;
940   }
941   }
942
943   // The GNU linker uses .note.GNU-stack section as a marker indicating
944   // that the code in the object file does not expect that the stack is
945   // executable (in terms of NX bit). If all input files have the marker,
946   // the GNU linker adds a PT_GNU_STACK segment to tells the loader to
947   // make the stack non-executable. Most object files have this section as
948   // of 2017.
949   //
950   // But making the stack non-executable is a norm today for security
951   // reasons. Failure to do so may result in a serious security issue.
952   // Therefore, we make LLD always add PT_GNU_STACK unless it is
953   // explicitly told to do otherwise (by -z execstack). Because the stack
954   // executable-ness is controlled solely by command line options,
955   // .note.GNU-stack sections are simply ignored.
956   if (name == ".note.GNU-stack")
957     return &InputSection::discarded;
958
959   // Object files that use processor features such as Intel Control-Flow
960   // Enforcement (CET) or AArch64 Branch Target Identification BTI, use a
961   // .note.gnu.property section containing a bitfield of feature bits like the
962   // GNU_PROPERTY_X86_FEATURE_1_IBT flag. Read a bitmap containing the flag.
963   //
964   // Since we merge bitmaps from multiple object files to create a new
965   // .note.gnu.property containing a single AND'ed bitmap, we discard an input
966   // file's .note.gnu.property section.
967   if (name == ".note.gnu.property") {
968     ArrayRef<uint8_t> contents = check(this->getObj().getSectionContents(&sec));
969     this->andFeatures = readAndFeatures(this, contents);
970     return &InputSection::discarded;
971   }
972
973   // Split stacks is a feature to support a discontiguous stack,
974   // commonly used in the programming language Go. For the details,
975   // see https://gcc.gnu.org/wiki/SplitStacks. An object file compiled
976   // for split stack will include a .note.GNU-split-stack section.
977   if (name == ".note.GNU-split-stack") {
978     if (config->relocatable) {
979       error("cannot mix split-stack and non-split-stack in a relocatable link");
980       return &InputSection::discarded;
981     }
982     this->splitStack = true;
983     return &InputSection::discarded;
984   }
985
986   // An object file cmpiled for split stack, but where some of the
987   // functions were compiled with the no_split_stack_attribute will
988   // include a .note.GNU-no-split-stack section.
989   if (name == ".note.GNU-no-split-stack") {
990     this->someNoSplitStack = true;
991     return &InputSection::discarded;
992   }
993
994   // The linkonce feature is a sort of proto-comdat. Some glibc i386 object
995   // files contain definitions of symbol "__x86.get_pc_thunk.bx" in linkonce
996   // sections. Drop those sections to avoid duplicate symbol errors.
997   // FIXME: This is glibc PR20543, we should remove this hack once that has been
998   // fixed for a while.
999   if (name == ".gnu.linkonce.t.__x86.get_pc_thunk.bx" ||
1000       name == ".gnu.linkonce.t.__i686.get_pc_thunk.bx")
1001     return &InputSection::discarded;
1002
1003   // If we are creating a new .build-id section, strip existing .build-id
1004   // sections so that the output won't have more than one .build-id.
1005   // This is not usually a problem because input object files normally don't
1006   // have .build-id sections, but you can create such files by
1007   // "ld.{bfd,gold,lld} -r --build-id", and we want to guard against it.
1008   if (name == ".note.gnu.build-id" && config->buildId != BuildIdKind::None)
1009     return &InputSection::discarded;
1010
1011   // The linker merges EH (exception handling) frames and creates a
1012   // .eh_frame_hdr section for runtime. So we handle them with a special
1013   // class. For relocatable outputs, they are just passed through.
1014   if (name == ".eh_frame" && !config->relocatable)
1015     return make<EhInputSection>(*this, sec, name);
1016
1017   if (shouldMerge(sec, name))
1018     return make<MergeInputSection>(*this, sec, name);
1019   return make<InputSection>(*this, sec, name);
1020 }
1021
1022 template <class ELFT>
1023 StringRef ObjFile<ELFT>::getSectionName(const Elf_Shdr &sec) {
1024   return CHECK(getObj().getSectionName(&sec, sectionStringTable), this);
1025 }
1026
1027 // Initialize this->Symbols. this->Symbols is a parallel array as
1028 // its corresponding ELF symbol table.
1029 template <class ELFT> void ObjFile<ELFT>::initializeSymbols() {
1030   ArrayRef<Elf_Sym> eSyms = this->getELFSyms<ELFT>();
1031   this->symbols.resize(eSyms.size());
1032
1033   // Our symbol table may have already been partially initialized
1034   // because of LazyObjFile.
1035   for (size_t i = 0, end = eSyms.size(); i != end; ++i)
1036     if (!this->symbols[i] && eSyms[i].getBinding() != STB_LOCAL)
1037       this->symbols[i] =
1038           symtab->insert(CHECK(eSyms[i].getName(this->stringTable), this));
1039
1040   // Fill this->Symbols. A symbol is either local or global.
1041   for (size_t i = 0, end = eSyms.size(); i != end; ++i) {
1042     const Elf_Sym &eSym = eSyms[i];
1043
1044     // Read symbol attributes.
1045     uint32_t secIdx = getSectionIndex(eSym);
1046     if (secIdx >= this->sections.size())
1047       fatal(toString(this) + ": invalid section index: " + Twine(secIdx));
1048
1049     InputSectionBase *sec = this->sections[secIdx];
1050     uint8_t binding = eSym.getBinding();
1051     uint8_t stOther = eSym.st_other;
1052     uint8_t type = eSym.getType();
1053     uint64_t value = eSym.st_value;
1054     uint64_t size = eSym.st_size;
1055     StringRefZ name = this->stringTable.data() + eSym.st_name;
1056
1057     // Handle local symbols. Local symbols are not added to the symbol
1058     // table because they are not visible from other object files. We
1059     // allocate symbol instances and add their pointers to Symbols.
1060     if (binding == STB_LOCAL) {
1061       if (eSym.getType() == STT_FILE)
1062         sourceFile = CHECK(eSym.getName(this->stringTable), this);
1063
1064       if (this->stringTable.size() <= eSym.st_name)
1065         fatal(toString(this) + ": invalid symbol name offset");
1066
1067       if (eSym.st_shndx == SHN_UNDEF)
1068         this->symbols[i] = make<Undefined>(this, name, binding, stOther, type);
1069       else if (sec == &InputSection::discarded)
1070         this->symbols[i] = make<Undefined>(this, name, binding, stOther, type,
1071                                            /*DiscardedSecIdx=*/secIdx);
1072       else
1073         this->symbols[i] =
1074             make<Defined>(this, name, binding, stOther, type, value, size, sec);
1075       continue;
1076     }
1077
1078     // Handle global undefined symbols.
1079     if (eSym.st_shndx == SHN_UNDEF) {
1080       this->symbols[i]->resolve(Undefined{this, name, binding, stOther, type});
1081       this->symbols[i]->referenced = true;
1082       continue;
1083     }
1084
1085     // Handle global common symbols.
1086     if (eSym.st_shndx == SHN_COMMON) {
1087       if (value == 0 || value >= UINT32_MAX)
1088         fatal(toString(this) + ": common symbol '" + StringRef(name.data) +
1089               "' has invalid alignment: " + Twine(value));
1090       this->symbols[i]->resolve(
1091           CommonSymbol{this, name, binding, stOther, type, value, size});
1092       continue;
1093     }
1094
1095     // If a defined symbol is in a discarded section, handle it as if it
1096     // were an undefined symbol. Such symbol doesn't comply with the
1097     // standard, but in practice, a .eh_frame often directly refer
1098     // COMDAT member sections, and if a comdat group is discarded, some
1099     // defined symbol in a .eh_frame becomes dangling symbols.
1100     if (sec == &InputSection::discarded) {
1101       this->symbols[i]->resolve(
1102           Undefined{this, name, binding, stOther, type, secIdx});
1103       continue;
1104     }
1105
1106     // Handle global defined symbols.
1107     if (binding == STB_GLOBAL || binding == STB_WEAK ||
1108         binding == STB_GNU_UNIQUE) {
1109       this->symbols[i]->resolve(
1110           Defined{this, name, binding, stOther, type, value, size, sec});
1111       continue;
1112     }
1113
1114     fatal(toString(this) + ": unexpected binding: " + Twine((int)binding));
1115   }
1116 }
1117
1118 ArchiveFile::ArchiveFile(std::unique_ptr<Archive> &&file)
1119     : InputFile(ArchiveKind, file->getMemoryBufferRef()),
1120       file(std::move(file)) {}
1121
1122 void ArchiveFile::parse() {
1123   for (const Archive::Symbol &sym : file->symbols())
1124     symtab->addSymbol(LazyArchive{*this, sym});
1125 }
1126
1127 // Returns a buffer pointing to a member file containing a given symbol.
1128 void ArchiveFile::fetch(const Archive::Symbol &sym) {
1129   Archive::Child c =
1130       CHECK(sym.getMember(), toString(this) +
1131                                  ": could not get the member for symbol " +
1132                                  toELFString(sym));
1133
1134   if (!seen.insert(c.getChildOffset()).second)
1135     return;
1136
1137   MemoryBufferRef mb =
1138       CHECK(c.getMemoryBufferRef(),
1139             toString(this) +
1140                 ": could not get the buffer for the member defining symbol " +
1141                 toELFString(sym));
1142
1143   if (tar && c.getParent()->isThin())
1144     tar->append(relativeToRoot(CHECK(c.getFullName(), this)), mb.getBuffer());
1145
1146   InputFile *file = createObjectFile(
1147       mb, getName(), c.getParent()->isThin() ? 0 : c.getChildOffset());
1148   file->groupId = groupId;
1149   parseFile(file);
1150 }
1151
1152 unsigned SharedFile::vernauxNum;
1153
1154 // Parse the version definitions in the object file if present, and return a
1155 // vector whose nth element contains a pointer to the Elf_Verdef for version
1156 // identifier n. Version identifiers that are not definitions map to nullptr.
1157 template <typename ELFT>
1158 static std::vector<const void *> parseVerdefs(const uint8_t *base,
1159                                               const typename ELFT::Shdr *sec) {
1160   if (!sec)
1161     return {};
1162
1163   // We cannot determine the largest verdef identifier without inspecting
1164   // every Elf_Verdef, but both bfd and gold assign verdef identifiers
1165   // sequentially starting from 1, so we predict that the largest identifier
1166   // will be verdefCount.
1167   unsigned verdefCount = sec->sh_info;
1168   std::vector<const void *> verdefs(verdefCount + 1);
1169
1170   // Build the Verdefs array by following the chain of Elf_Verdef objects
1171   // from the start of the .gnu.version_d section.
1172   const uint8_t *verdef = base + sec->sh_offset;
1173   for (unsigned i = 0; i != verdefCount; ++i) {
1174     auto *curVerdef = reinterpret_cast<const typename ELFT::Verdef *>(verdef);
1175     verdef += curVerdef->vd_next;
1176     unsigned verdefIndex = curVerdef->vd_ndx;
1177     verdefs.resize(verdefIndex + 1);
1178     verdefs[verdefIndex] = curVerdef;
1179   }
1180   return verdefs;
1181 }
1182
1183 // We do not usually care about alignments of data in shared object
1184 // files because the loader takes care of it. However, if we promote a
1185 // DSO symbol to point to .bss due to copy relocation, we need to keep
1186 // the original alignment requirements. We infer it in this function.
1187 template <typename ELFT>
1188 static uint64_t getAlignment(ArrayRef<typename ELFT::Shdr> sections,
1189                              const typename ELFT::Sym &sym) {
1190   uint64_t ret = UINT64_MAX;
1191   if (sym.st_value)
1192     ret = 1ULL << countTrailingZeros((uint64_t)sym.st_value);
1193   if (0 < sym.st_shndx && sym.st_shndx < sections.size())
1194     ret = std::min<uint64_t>(ret, sections[sym.st_shndx].sh_addralign);
1195   return (ret > UINT32_MAX) ? 0 : ret;
1196 }
1197
1198 // Fully parse the shared object file.
1199 //
1200 // This function parses symbol versions. If a DSO has version information,
1201 // the file has a ".gnu.version_d" section which contains symbol version
1202 // definitions. Each symbol is associated to one version through a table in
1203 // ".gnu.version" section. That table is a parallel array for the symbol
1204 // table, and each table entry contains an index in ".gnu.version_d".
1205 //
1206 // The special index 0 is reserved for VERF_NDX_LOCAL and 1 is for
1207 // VER_NDX_GLOBAL. There's no table entry for these special versions in
1208 // ".gnu.version_d".
1209 //
1210 // The file format for symbol versioning is perhaps a bit more complicated
1211 // than necessary, but you can easily understand the code if you wrap your
1212 // head around the data structure described above.
1213 template <class ELFT> void SharedFile::parse() {
1214   using Elf_Dyn = typename ELFT::Dyn;
1215   using Elf_Shdr = typename ELFT::Shdr;
1216   using Elf_Sym = typename ELFT::Sym;
1217   using Elf_Verdef = typename ELFT::Verdef;
1218   using Elf_Versym = typename ELFT::Versym;
1219
1220   ArrayRef<Elf_Dyn> dynamicTags;
1221   const ELFFile<ELFT> obj = this->getObj<ELFT>();
1222   ArrayRef<Elf_Shdr> sections = CHECK(obj.sections(), this);
1223
1224   const Elf_Shdr *versymSec = nullptr;
1225   const Elf_Shdr *verdefSec = nullptr;
1226
1227   // Search for .dynsym, .dynamic, .symtab, .gnu.version and .gnu.version_d.
1228   for (const Elf_Shdr &sec : sections) {
1229     switch (sec.sh_type) {
1230     default:
1231       continue;
1232     case SHT_DYNAMIC:
1233       dynamicTags =
1234           CHECK(obj.template getSectionContentsAsArray<Elf_Dyn>(&sec), this);
1235       break;
1236     case SHT_GNU_versym:
1237       versymSec = &sec;
1238       break;
1239     case SHT_GNU_verdef:
1240       verdefSec = &sec;
1241       break;
1242     }
1243   }
1244
1245   if (versymSec && numELFSyms == 0) {
1246     error("SHT_GNU_versym should be associated with symbol table");
1247     return;
1248   }
1249
1250   // Search for a DT_SONAME tag to initialize this->soName.
1251   for (const Elf_Dyn &dyn : dynamicTags) {
1252     if (dyn.d_tag == DT_NEEDED) {
1253       uint64_t val = dyn.getVal();
1254       if (val >= this->stringTable.size())
1255         fatal(toString(this) + ": invalid DT_NEEDED entry");
1256       dtNeeded.push_back(this->stringTable.data() + val);
1257     } else if (dyn.d_tag == DT_SONAME) {
1258       uint64_t val = dyn.getVal();
1259       if (val >= this->stringTable.size())
1260         fatal(toString(this) + ": invalid DT_SONAME entry");
1261       soName = this->stringTable.data() + val;
1262     }
1263   }
1264
1265   // DSOs are uniquified not by filename but by soname.
1266   DenseMap<StringRef, SharedFile *>::iterator it;
1267   bool wasInserted;
1268   std::tie(it, wasInserted) = symtab->soNames.try_emplace(soName, this);
1269
1270   // If a DSO appears more than once on the command line with and without
1271   // --as-needed, --no-as-needed takes precedence over --as-needed because a
1272   // user can add an extra DSO with --no-as-needed to force it to be added to
1273   // the dependency list.
1274   it->second->isNeeded |= isNeeded;
1275   if (!wasInserted)
1276     return;
1277
1278   sharedFiles.push_back(this);
1279
1280   verdefs = parseVerdefs<ELFT>(obj.base(), verdefSec);
1281
1282   // Parse ".gnu.version" section which is a parallel array for the symbol
1283   // table. If a given file doesn't have a ".gnu.version" section, we use
1284   // VER_NDX_GLOBAL.
1285   size_t size = numELFSyms - firstGlobal;
1286   std::vector<uint32_t> versyms(size, VER_NDX_GLOBAL);
1287   if (versymSec) {
1288     ArrayRef<Elf_Versym> versym =
1289         CHECK(obj.template getSectionContentsAsArray<Elf_Versym>(versymSec),
1290               this)
1291             .slice(firstGlobal);
1292     for (size_t i = 0; i < size; ++i)
1293       versyms[i] = versym[i].vs_index;
1294   }
1295
1296   // System libraries can have a lot of symbols with versions. Using a
1297   // fixed buffer for computing the versions name (foo@ver) can save a
1298   // lot of allocations.
1299   SmallString<0> versionedNameBuffer;
1300
1301   // Add symbols to the symbol table.
1302   ArrayRef<Elf_Sym> syms = this->getGlobalELFSyms<ELFT>();
1303   for (size_t i = 0; i < syms.size(); ++i) {
1304     const Elf_Sym &sym = syms[i];
1305
1306     // ELF spec requires that all local symbols precede weak or global
1307     // symbols in each symbol table, and the index of first non-local symbol
1308     // is stored to sh_info. If a local symbol appears after some non-local
1309     // symbol, that's a violation of the spec.
1310     StringRef name = CHECK(sym.getName(this->stringTable), this);
1311     if (sym.getBinding() == STB_LOCAL) {
1312       warn("found local symbol '" + name +
1313            "' in global part of symbol table in file " + toString(this));
1314       continue;
1315     }
1316
1317     if (sym.isUndefined()) {
1318       Symbol *s = symtab->addSymbol(
1319           Undefined{this, name, sym.getBinding(), sym.st_other, sym.getType()});
1320       s->exportDynamic = true;
1321       continue;
1322     }
1323
1324     // MIPS BFD linker puts _gp_disp symbol into DSO files and incorrectly
1325     // assigns VER_NDX_LOCAL to this section global symbol. Here is a
1326     // workaround for this bug.
1327     uint32_t idx = versyms[i] & ~VERSYM_HIDDEN;
1328     if (config->emachine == EM_MIPS && idx == VER_NDX_LOCAL &&
1329         name == "_gp_disp")
1330       continue;
1331
1332     uint32_t alignment = getAlignment<ELFT>(sections, sym);
1333     if (!(versyms[i] & VERSYM_HIDDEN)) {
1334       symtab->addSymbol(SharedSymbol{*this, name, sym.getBinding(),
1335                                      sym.st_other, sym.getType(), sym.st_value,
1336                                      sym.st_size, alignment, idx});
1337     }
1338
1339     // Also add the symbol with the versioned name to handle undefined symbols
1340     // with explicit versions.
1341     if (idx == VER_NDX_GLOBAL)
1342       continue;
1343
1344     if (idx >= verdefs.size() || idx == VER_NDX_LOCAL) {
1345       error("corrupt input file: version definition index " + Twine(idx) +
1346             " for symbol " + name + " is out of bounds\n>>> defined in " +
1347             toString(this));
1348       continue;
1349     }
1350
1351     StringRef verName =
1352         this->stringTable.data() +
1353         reinterpret_cast<const Elf_Verdef *>(verdefs[idx])->getAux()->vda_name;
1354     versionedNameBuffer.clear();
1355     name = (name + "@" + verName).toStringRef(versionedNameBuffer);
1356     symtab->addSymbol(SharedSymbol{*this, saver.save(name), sym.getBinding(),
1357                                    sym.st_other, sym.getType(), sym.st_value,
1358                                    sym.st_size, alignment, idx});
1359   }
1360 }
1361
1362 static ELFKind getBitcodeELFKind(const Triple &t) {
1363   if (t.isLittleEndian())
1364     return t.isArch64Bit() ? ELF64LEKind : ELF32LEKind;
1365   return t.isArch64Bit() ? ELF64BEKind : ELF32BEKind;
1366 }
1367
1368 static uint8_t getBitcodeMachineKind(StringRef path, const Triple &t) {
1369   switch (t.getArch()) {
1370   case Triple::aarch64:
1371     return EM_AARCH64;
1372   case Triple::amdgcn:
1373   case Triple::r600:
1374     return EM_AMDGPU;
1375   case Triple::arm:
1376   case Triple::thumb:
1377     return EM_ARM;
1378   case Triple::avr:
1379     return EM_AVR;
1380   case Triple::mips:
1381   case Triple::mipsel:
1382   case Triple::mips64:
1383   case Triple::mips64el:
1384     return EM_MIPS;
1385   case Triple::msp430:
1386     return EM_MSP430;
1387   case Triple::ppc:
1388     return EM_PPC;
1389   case Triple::ppc64:
1390   case Triple::ppc64le:
1391     return EM_PPC64;
1392   case Triple::riscv32:
1393   case Triple::riscv64:
1394     return EM_RISCV;
1395   case Triple::x86:
1396     return t.isOSIAMCU() ? EM_IAMCU : EM_386;
1397   case Triple::x86_64:
1398     return EM_X86_64;
1399   default:
1400     error(path + ": could not infer e_machine from bitcode target triple " +
1401           t.str());
1402     return EM_NONE;
1403   }
1404 }
1405
1406 BitcodeFile::BitcodeFile(MemoryBufferRef mb, StringRef archiveName,
1407                          uint64_t offsetInArchive)
1408     : InputFile(BitcodeKind, mb) {
1409   this->archiveName = std::string(archiveName);
1410
1411   std::string path = mb.getBufferIdentifier().str();
1412   if (config->thinLTOIndexOnly)
1413     path = replaceThinLTOSuffix(mb.getBufferIdentifier());
1414
1415   // ThinLTO assumes that all MemoryBufferRefs given to it have a unique
1416   // name. If two archives define two members with the same name, this
1417   // causes a collision which result in only one of the objects being taken
1418   // into consideration at LTO time (which very likely causes undefined
1419   // symbols later in the link stage). So we append file offset to make
1420   // filename unique.
1421   StringRef name = archiveName.empty()
1422                        ? saver.save(path)
1423                        : saver.save(archiveName + "(" + path + " at " +
1424                                     utostr(offsetInArchive) + ")");
1425   MemoryBufferRef mbref(mb.getBuffer(), name);
1426
1427   obj = CHECK(lto::InputFile::create(mbref), this);
1428
1429   Triple t(obj->getTargetTriple());
1430   ekind = getBitcodeELFKind(t);
1431   emachine = getBitcodeMachineKind(mb.getBufferIdentifier(), t);
1432 }
1433
1434 static uint8_t mapVisibility(GlobalValue::VisibilityTypes gvVisibility) {
1435   switch (gvVisibility) {
1436   case GlobalValue::DefaultVisibility:
1437     return STV_DEFAULT;
1438   case GlobalValue::HiddenVisibility:
1439     return STV_HIDDEN;
1440   case GlobalValue::ProtectedVisibility:
1441     return STV_PROTECTED;
1442   }
1443   llvm_unreachable("unknown visibility");
1444 }
1445
1446 template <class ELFT>
1447 static Symbol *createBitcodeSymbol(const std::vector<bool> &keptComdats,
1448                                    const lto::InputFile::Symbol &objSym,
1449                                    BitcodeFile &f) {
1450   StringRef name = saver.save(objSym.getName());
1451   uint8_t binding = objSym.isWeak() ? STB_WEAK : STB_GLOBAL;
1452   uint8_t type = objSym.isTLS() ? STT_TLS : STT_NOTYPE;
1453   uint8_t visibility = mapVisibility(objSym.getVisibility());
1454   bool canOmitFromDynSym = objSym.canBeOmittedFromSymbolTable();
1455
1456   int c = objSym.getComdatIndex();
1457   if (objSym.isUndefined() || (c != -1 && !keptComdats[c])) {
1458     Undefined newSym(&f, name, binding, visibility, type);
1459     if (canOmitFromDynSym)
1460       newSym.exportDynamic = false;
1461     Symbol *ret = symtab->addSymbol(newSym);
1462     ret->referenced = true;
1463     return ret;
1464   }
1465
1466   if (objSym.isCommon())
1467     return symtab->addSymbol(
1468         CommonSymbol{&f, name, binding, visibility, STT_OBJECT,
1469                      objSym.getCommonAlignment(), objSym.getCommonSize()});
1470
1471   Defined newSym(&f, name, binding, visibility, type, 0, 0, nullptr);
1472   if (canOmitFromDynSym)
1473     newSym.exportDynamic = false;
1474   return symtab->addSymbol(newSym);
1475 }
1476
1477 template <class ELFT> void BitcodeFile::parse() {
1478   std::vector<bool> keptComdats;
1479   for (StringRef s : obj->getComdatTable())
1480     keptComdats.push_back(
1481         symtab->comdatGroups.try_emplace(CachedHashStringRef(s), this).second);
1482
1483   for (const lto::InputFile::Symbol &objSym : obj->symbols())
1484     symbols.push_back(createBitcodeSymbol<ELFT>(keptComdats, objSym, *this));
1485
1486   for (auto l : obj->getDependentLibraries())
1487     addDependentLibrary(l, this);
1488 }
1489
1490 void BinaryFile::parse() {
1491   ArrayRef<uint8_t> data = arrayRefFromStringRef(mb.getBuffer());
1492   auto *section = make<InputSection>(this, SHF_ALLOC | SHF_WRITE, SHT_PROGBITS,
1493                                      8, data, ".data");
1494   sections.push_back(section);
1495
1496   // For each input file foo that is embedded to a result as a binary
1497   // blob, we define _binary_foo_{start,end,size} symbols, so that
1498   // user programs can access blobs by name. Non-alphanumeric
1499   // characters in a filename are replaced with underscore.
1500   std::string s = "_binary_" + mb.getBufferIdentifier().str();
1501   for (size_t i = 0; i < s.size(); ++i)
1502     if (!isAlnum(s[i]))
1503       s[i] = '_';
1504
1505   symtab->addSymbol(Defined{nullptr, saver.save(s + "_start"), STB_GLOBAL,
1506                             STV_DEFAULT, STT_OBJECT, 0, 0, section});
1507   symtab->addSymbol(Defined{nullptr, saver.save(s + "_end"), STB_GLOBAL,
1508                             STV_DEFAULT, STT_OBJECT, data.size(), 0, section});
1509   symtab->addSymbol(Defined{nullptr, saver.save(s + "_size"), STB_GLOBAL,
1510                             STV_DEFAULT, STT_OBJECT, data.size(), 0, nullptr});
1511 }
1512
1513 InputFile *createObjectFile(MemoryBufferRef mb, StringRef archiveName,
1514                             uint64_t offsetInArchive) {
1515   if (isBitcode(mb))
1516     return make<BitcodeFile>(mb, archiveName, offsetInArchive);
1517
1518   switch (getELFKind(mb, archiveName)) {
1519   case ELF32LEKind:
1520     return make<ObjFile<ELF32LE>>(mb, archiveName);
1521   case ELF32BEKind:
1522     return make<ObjFile<ELF32BE>>(mb, archiveName);
1523   case ELF64LEKind:
1524     return make<ObjFile<ELF64LE>>(mb, archiveName);
1525   case ELF64BEKind:
1526     return make<ObjFile<ELF64BE>>(mb, archiveName);
1527   default:
1528     llvm_unreachable("getELFKind");
1529   }
1530 }
1531
1532 void LazyObjFile::fetch() {
1533   if (mb.getBuffer().empty())
1534     return;
1535
1536   InputFile *file = createObjectFile(mb, archiveName, offsetInArchive);
1537   file->groupId = groupId;
1538
1539   mb = {};
1540
1541   // Copy symbol vector so that the new InputFile doesn't have to
1542   // insert the same defined symbols to the symbol table again.
1543   file->symbols = std::move(symbols);
1544
1545   parseFile(file);
1546 }
1547
1548 template <class ELFT> void LazyObjFile::parse() {
1549   using Elf_Sym = typename ELFT::Sym;
1550
1551   // A lazy object file wraps either a bitcode file or an ELF file.
1552   if (isBitcode(this->mb)) {
1553     std::unique_ptr<lto::InputFile> obj =
1554         CHECK(lto::InputFile::create(this->mb), this);
1555     for (const lto::InputFile::Symbol &sym : obj->symbols()) {
1556       if (sym.isUndefined())
1557         continue;
1558       symtab->addSymbol(LazyObject{*this, saver.save(sym.getName())});
1559     }
1560     return;
1561   }
1562
1563   if (getELFKind(this->mb, archiveName) != config->ekind) {
1564     error("incompatible file: " + this->mb.getBufferIdentifier());
1565     return;
1566   }
1567
1568   // Find a symbol table.
1569   ELFFile<ELFT> obj = check(ELFFile<ELFT>::create(mb.getBuffer()));
1570   ArrayRef<typename ELFT::Shdr> sections = CHECK(obj.sections(), this);
1571
1572   for (const typename ELFT::Shdr &sec : sections) {
1573     if (sec.sh_type != SHT_SYMTAB)
1574       continue;
1575
1576     // A symbol table is found.
1577     ArrayRef<Elf_Sym> eSyms = CHECK(obj.symbols(&sec), this);
1578     uint32_t firstGlobal = sec.sh_info;
1579     StringRef strtab = CHECK(obj.getStringTableForSymtab(sec, sections), this);
1580     this->symbols.resize(eSyms.size());
1581
1582     // Get existing symbols or insert placeholder symbols.
1583     for (size_t i = firstGlobal, end = eSyms.size(); i != end; ++i)
1584       if (eSyms[i].st_shndx != SHN_UNDEF)
1585         this->symbols[i] = symtab->insert(CHECK(eSyms[i].getName(strtab), this));
1586
1587     // Replace existing symbols with LazyObject symbols.
1588     //
1589     // resolve() may trigger this->fetch() if an existing symbol is an
1590     // undefined symbol. If that happens, this LazyObjFile has served
1591     // its purpose, and we can exit from the loop early.
1592     for (Symbol *sym : this->symbols) {
1593       if (!sym)
1594         continue;
1595       sym->resolve(LazyObject{*this, sym->getName()});
1596
1597       // MemoryBuffer is emptied if this file is instantiated as ObjFile.
1598       if (mb.getBuffer().empty())
1599         return;
1600     }
1601     return;
1602   }
1603 }
1604
1605 std::string replaceThinLTOSuffix(StringRef path) {
1606   StringRef suffix = config->thinLTOObjectSuffixReplace.first;
1607   StringRef repl = config->thinLTOObjectSuffixReplace.second;
1608
1609   if (path.consume_back(suffix))
1610     return (path + repl).str();
1611   return std::string(path);
1612 }
1613
1614 template void BitcodeFile::parse<ELF32LE>();
1615 template void BitcodeFile::parse<ELF32BE>();
1616 template void BitcodeFile::parse<ELF64LE>();
1617 template void BitcodeFile::parse<ELF64BE>();
1618
1619 template void LazyObjFile::parse<ELF32LE>();
1620 template void LazyObjFile::parse<ELF32BE>();
1621 template void LazyObjFile::parse<ELF64LE>();
1622 template void LazyObjFile::parse<ELF64BE>();
1623
1624 template class ObjFile<ELF32LE>;
1625 template class ObjFile<ELF32BE>;
1626 template class ObjFile<ELF64LE>;
1627 template class ObjFile<ELF64BE>;
1628
1629 template void SharedFile::parse<ELF32LE>();
1630 template void SharedFile::parse<ELF32BE>();
1631 template void SharedFile::parse<ELF64LE>();
1632 template void SharedFile::parse<ELF64BE>();
1633
1634 } // namespace elf
1635 } // namespace lld