contrib/llvm/tools/lld/ELF/InputSection.cpp

   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 "EhFrame.h"
  13 #include "InputFiles.h"
  14 #include "LinkerScript.h"
  15 #include "OutputSections.h"
  16 #include "Relocations.h"
  17 #include "Symbols.h"
  18 #include "SyntheticSections.h"
  19 #include "Target.h"
  20 #include "Thunks.h"
  21 #include "lld/Common/ErrorHandler.h"
  22 #include "lld/Common/Memory.h"
  23 #include "llvm/Object/Decompressor.h"
  24 #include "llvm/Support/Compiler.h"
  25 #include "llvm/Support/Compression.h"
  26 #include "llvm/Support/Endian.h"
  27 #include "llvm/Support/Threading.h"
  28 #include "llvm/Support/xxhash.h"
  29 #include <mutex>
  30
  31 using namespace llvm;
  32 using namespace llvm::ELF;
  33 using namespace llvm::object;
  34 using namespace llvm::support;
  35 using namespace llvm::support::endian;
  36 using namespace llvm::sys;
  37
  38 using namespace lld;
  39 using namespace lld::elf;
  40
  41 std::vector<InputSectionBase *> elf::InputSections;
  42
  43 // Returns a string to construct an error message.
  44 std::string lld::toString(const InputSectionBase *Sec) {
  45   return (toString(Sec->File) + ":(" + Sec->Name + ")").str();
  46 }
  47
  48 DenseMap<SectionBase *, int> elf::buildSectionOrder() {
  49   DenseMap<SectionBase *, int> SectionOrder;
  50   if (Config->SymbolOrderingFile.empty())
  51     return SectionOrder;
  52
  53   // Build a map from symbols to their priorities. Symbols that didn't
  54   // appear in the symbol ordering file have the lowest priority 0.
  55   // All explicitly mentioned symbols have negative (higher) priorities.
  56   DenseMap<StringRef, int> SymbolOrder;
  57   int Priority = -Config->SymbolOrderingFile.size();
  58   for (StringRef S : Config->SymbolOrderingFile)
  59     SymbolOrder.insert({S, Priority++});
  60
  61   // Build a map from sections to their priorities.
  62   for (InputFile *File : ObjectFiles) {
  63     for (Symbol *Sym : File->getSymbols()) {
  64       auto *D = dyn_cast<Defined>(Sym);
  65       if (!D || !D->Section)
  66         continue;
  67       int &Priority = SectionOrder[D->Section];
  68       Priority = std::min(Priority, SymbolOrder.lookup(D->getName()));
  69     }
  70   }
  71   return SectionOrder;
  72 }
  73
  74 template <class ELFT>
  75 static ArrayRef<uint8_t> getSectionContents(ObjFile<ELFT> &File,
  76                                             const typename ELFT::Shdr &Hdr) {
  77   if (Hdr.sh_type == SHT_NOBITS)
  78     return makeArrayRef<uint8_t>(nullptr, Hdr.sh_size);
  79   return check(File.getObj().getSectionContents(&Hdr));
  80 }
  81
  82 InputSectionBase::InputSectionBase(InputFile *File, uint64_t Flags,
  83                                    uint32_t Type, uint64_t Entsize,
  84                                    uint32_t Link, uint32_t Info,
  85                                    uint32_t Alignment, ArrayRef<uint8_t> Data,
  86                                    StringRef Name, Kind SectionKind)
  87     : SectionBase(SectionKind, Name, Flags, Entsize, Alignment, Type, Info,
  88                   Link),
  89       File(File), Data(Data) {
  90   // In order to reduce memory allocation, we assume that mergeable
  91   // sections are smaller than 4 GiB, which is not an unreasonable
  92   // assumption as of 2017.
  93   if (SectionKind == SectionBase::Merge && Data.size() > UINT32_MAX)
  94     error(toString(this) + ": section too large");
  95
  96   NumRelocations = 0;
  97   AreRelocsRela = false;
  98
  99   // The ELF spec states that a value of 0 means the section has
 100   // no alignment constraits.
 101   uint32_t V = std::max<uint64_t>(Alignment, 1);
 102   if (!isPowerOf2_64(V))
 103     fatal(toString(File) + ": section sh_addralign is not a power of 2");
 104   this->Alignment = V;
 105 }
 106
 107 // Drop SHF_GROUP bit unless we are producing a re-linkable object file.
 108 // SHF_GROUP is a marker that a section belongs to some comdat group.
 109 // That flag doesn't make sense in an executable.
 110 static uint64_t getFlags(uint64_t Flags) {
 111   Flags &= ~(uint64_t)SHF_INFO_LINK;
 112   if (!Config->Relocatable)
 113     Flags &= ~(uint64_t)SHF_GROUP;
 114   return Flags;
 115 }
 116
 117 // GNU assembler 2.24 and LLVM 4.0.0's MC (the newest release as of
 118 // March 2017) fail to infer section types for sections starting with
 119 // ".init_array." or ".fini_array.". They set SHT_PROGBITS instead of
 120 // SHF_INIT_ARRAY. As a result, the following assembler directive
 121 // creates ".init_array.100" with SHT_PROGBITS, for example.
 122 //
 123 //   .section .init_array.100, "aw"
 124 //
 125 // This function forces SHT_{INIT,FINI}_ARRAY so that we can handle
 126 // incorrect inputs as if they were correct from the beginning.
 127 static uint64_t getType(uint64_t Type, StringRef Name) {
 128   if (Type == SHT_PROGBITS && Name.startswith(".init_array."))
 129     return SHT_INIT_ARRAY;
 130   if (Type == SHT_PROGBITS && Name.startswith(".fini_array."))
 131     return SHT_FINI_ARRAY;
 132   return Type;
 133 }
 134
 135 template <class ELFT>
 136 InputSectionBase::InputSectionBase(ObjFile<ELFT> &File,
 137                                    const typename ELFT::Shdr &Hdr,
 138                                    StringRef Name, Kind SectionKind)
 139     : InputSectionBase(&File, getFlags(Hdr.sh_flags),
 140                        getType(Hdr.sh_type, Name), Hdr.sh_entsize, Hdr.sh_link,
 141                        Hdr.sh_info, Hdr.sh_addralign,
 142                        getSectionContents(File, Hdr), Name, SectionKind) {
 143   // We reject object files having insanely large alignments even though
 144   // they are allowed by the spec. I think 4GB is a reasonable limitation.
 145   // We might want to relax this in the future.
 146   if (Hdr.sh_addralign > UINT32_MAX)
 147     fatal(toString(&File) + ": section sh_addralign is too large");
 148 }
 149
 150 size_t InputSectionBase::getSize() const {
 151   if (auto *S = dyn_cast<SyntheticSection>(this))
 152     return S->getSize();
 153
 154   return Data.size();
 155 }
 156
 157 uint64_t InputSectionBase::getOffsetInFile() const {
 158   const uint8_t *FileStart = (const uint8_t *)File->MB.getBufferStart();
 159   const uint8_t *SecStart = Data.begin();
 160   return SecStart - FileStart;
 161 }
 162
 163 uint64_t SectionBase::getOffset(uint64_t Offset) const {
 164   switch (kind()) {
 165   case Output: {
 166     auto *OS = cast<OutputSection>(this);
 167     // For output sections we treat offset -1 as the end of the section.
 168     return Offset == uint64_t(-1) ? OS->Size : Offset;
 169   }
 170   case Regular:
 171     return cast<InputSection>(this)->OutSecOff + Offset;
 172   case Synthetic: {
 173     auto *IS = cast<InputSection>(this);
 174     // For synthetic sections we treat offset -1 as the end of the section.
 175     return IS->OutSecOff + (Offset == uint64_t(-1) ? IS->getSize() : Offset);
 176   }
 177   case EHFrame:
 178     // The file crtbeginT.o has relocations pointing to the start of an empty
 179     // .eh_frame that is known to be the first in the link. It does that to
 180     // identify the start of the output .eh_frame.
 181     return Offset;
 182   case Merge:
 183     const MergeInputSection *MS = cast<MergeInputSection>(this);
 184     if (InputSection *IS = MS->getParent())
 185       return IS->OutSecOff + MS->getOffset(Offset);
 186     return MS->getOffset(Offset);
 187   }
 188   llvm_unreachable("invalid section kind");
 189 }
 190
 191 OutputSection *SectionBase::getOutputSection() {
 192   InputSection *Sec;
 193   if (auto *IS = dyn_cast<InputSection>(this))
 194     return IS->getParent();
 195   else if (auto *MS = dyn_cast<MergeInputSection>(this))
 196     Sec = MS->getParent();
 197   else if (auto *EH = dyn_cast<EhInputSection>(this))
 198     Sec = EH->getParent();
 199   else
 200     return cast<OutputSection>(this);
 201   return Sec ? Sec->getParent() : nullptr;
 202 }
 203
 204 // Uncompress section contents if required. Note that this function
 205 // is called from parallelForEach, so it must be thread-safe.
 206 void InputSectionBase::maybeUncompress() {
 207   if (UncompressBuf || !Decompressor::isCompressedELFSection(Flags, Name))
 208     return;
 209
 210   Decompressor Dec = check(Decompressor::create(Name, toStringRef(Data),
 211                                                 Config->IsLE, Config->Is64));
 212
 213   size_t Size = Dec.getDecompressedSize();
 214   UncompressBuf.reset(new char[Size]());
 215   if (Error E = Dec.decompress({UncompressBuf.get(), Size}))
 216     fatal(toString(this) +
 217           ": decompress failed: " + llvm::toString(std::move(E)));
 218
 219   Data = makeArrayRef((uint8_t *)UncompressBuf.get(), Size);
 220   Flags &= ~(uint64_t)SHF_COMPRESSED;
 221 }
 222
 223 InputSection *InputSectionBase::getLinkOrderDep() const {
 224   if ((Flags & SHF_LINK_ORDER) && Link != 0) {
 225     InputSectionBase *L = File->getSections()[Link];
 226     if (auto *IS = dyn_cast<InputSection>(L))
 227       return IS;
 228     error("a section with SHF_LINK_ORDER should not refer a non-regular "
 229           "section: " +
 230           toString(L));
 231   }
 232   return nullptr;
 233 }
 234
 235 // Returns a source location string. Used to construct an error message.
 236 template <class ELFT>
 237 std::string InputSectionBase::getLocation(uint64_t Offset) {
 238   // We don't have file for synthetic sections.
 239   if (getFile<ELFT>() == nullptr)
 240     return (Config->OutputFile + ":(" + Name + "+0x" + utohexstr(Offset) + ")")
 241         .str();
 242
 243   // First check if we can get desired values from debugging information.
 244   std::string LineInfo = getFile<ELFT>()->getLineInfo(this, Offset);
 245   if (!LineInfo.empty())
 246     return LineInfo;
 247
 248   // File->SourceFile contains STT_FILE symbol that contains a
 249   // source file name. If it's missing, we use an object file name.
 250   std::string SrcFile = getFile<ELFT>()->SourceFile;
 251   if (SrcFile.empty())
 252     SrcFile = toString(File);
 253
 254   // Find a function symbol that encloses a given location.
 255   for (Symbol *B : File->getSymbols())
 256     if (auto *D = dyn_cast<Defined>(B))
 257       if (D->Section == this && D->Type == STT_FUNC)
 258         if (D->Value <= Offset && Offset < D->Value + D->Size)
 259           return SrcFile + ":(function " + toString(*D) + ")";
 260
 261   // If there's no symbol, print out the offset in the section.
 262   return (SrcFile + ":(" + Name + "+0x" + utohexstr(Offset) + ")").str();
 263 }
 264
 265 // This function is intended to be used for constructing an error message.
 266 // The returned message looks like this:
 267 //
 268 //   foo.c:42 (/home/alice/possibly/very/long/path/foo.c:42)
 269 //
 270 //  Returns an empty string if there's no way to get line info.
 271 std::string InputSectionBase::getSrcMsg(const Symbol &Sym, uint64_t Offset) {
 272   // Synthetic sections don't have input files.
 273   if (!File)
 274     return "";
 275   return File->getSrcMsg(Sym, *this, Offset);
 276 }
 277
 278 // Returns a filename string along with an optional section name. This
 279 // function is intended to be used for constructing an error
 280 // message. The returned message looks like this:
 281 //
 282 //   path/to/foo.o:(function bar)
 283 //
 284 // or
 285 //
 286 //   path/to/foo.o:(function bar) in archive path/to/bar.a
 287 std::string InputSectionBase::getObjMsg(uint64_t Off) {
 288   // Synthetic sections don't have input files.
 289   if (!File)
 290     return ("<internal>:(" + Name + "+0x" + utohexstr(Off) + ")").str();
 291   std::string Filename = File->getName();
 292
 293   std::string Archive;
 294   if (!File->ArchiveName.empty())
 295     Archive = (" in archive " + File->ArchiveName).str();
 296
 297   // Find a symbol that encloses a given location.
 298   for (Symbol *B : File->getSymbols())
 299     if (auto *D = dyn_cast<Defined>(B))
 300       if (D->Section == this && D->Value <= Off && Off < D->Value + D->Size)
 301         return Filename + ":(" + toString(*D) + ")" + Archive;
 302
 303   // If there's no symbol, print out the offset in the section.
 304   return (Filename + ":(" + Name + "+0x" + utohexstr(Off) + ")" + Archive)
 305       .str();
 306 }
 307
 308 InputSection InputSection::Discarded(nullptr, 0, 0, 0, ArrayRef<uint8_t>(), "");
 309
 310 InputSection::InputSection(InputFile *F, uint64_t Flags, uint32_t Type,
 311                            uint32_t Alignment, ArrayRef<uint8_t> Data,
 312                            StringRef Name, Kind K)
 313     : InputSectionBase(F, Flags, Type,
 314                        /*Entsize*/ 0, /*Link*/ 0, /*Info*/ 0, Alignment, Data,
 315                        Name, K) {}
 316
 317 template <class ELFT>
 318 InputSection::InputSection(ObjFile<ELFT> &F, const typename ELFT::Shdr &Header,
 319                            StringRef Name)
 320     : InputSectionBase(F, Header, Name, InputSectionBase::Regular) {}
 321
 322 bool InputSection::classof(const SectionBase *S) {
 323   return S->kind() == SectionBase::Regular ||
 324          S->kind() == SectionBase::Synthetic;
 325 }
 326
 327 OutputSection *InputSection::getParent() const {
 328   return cast_or_null<OutputSection>(Parent);
 329 }
 330
 331 // Copy SHT_GROUP section contents. Used only for the -r option.
 332 template <class ELFT> void InputSection::copyShtGroup(uint8_t *Buf) {
 333   // ELFT::Word is the 32-bit integral type in the target endianness.
 334   typedef typename ELFT::Word u32;
 335   ArrayRef<u32> From = getDataAs<u32>();
 336   auto *To = reinterpret_cast<u32 *>(Buf);
 337
 338   // The first entry is not a section number but a flag.
 339   *To++ = From[0];
 340
 341   // Adjust section numbers because section numbers in an input object
 342   // files are different in the output.
 343   ArrayRef<InputSectionBase *> Sections = File->getSections();
 344   for (uint32_t Idx : From.slice(1))
 345     *To++ = Sections[Idx]->getOutputSection()->SectionIndex;
 346 }
 347
 348 InputSectionBase *InputSection::getRelocatedSection() {
 349   assert(Type == SHT_RELA || Type == SHT_REL);
 350   ArrayRef<InputSectionBase *> Sections = File->getSections();
 351   return Sections[Info];
 352 }
 353
 354 // This is used for -r and --emit-relocs. We can't use memcpy to copy
 355 // relocations because we need to update symbol table offset and section index
 356 // for each relocation. So we copy relocations one by one.
 357 template <class ELFT, class RelTy>
 358 void InputSection::copyRelocations(uint8_t *Buf, ArrayRef<RelTy> Rels) {
 359   InputSectionBase *Sec = getRelocatedSection();
 360
 361   for (const RelTy &Rel : Rels) {
 362     RelType Type = Rel.getType(Config->IsMips64EL);
 363     Symbol &Sym = getFile<ELFT>()->getRelocTargetSym(Rel);
 364
 365     auto *P = reinterpret_cast<typename ELFT::Rela *>(Buf);
 366     Buf += sizeof(RelTy);
 367
 368     if (Config->IsRela)
 369       P->r_addend = getAddend<ELFT>(Rel);
 370
 371     // Output section VA is zero for -r, so r_offset is an offset within the
 372     // section, but for --emit-relocs it is an virtual address.
 373     P->r_offset = Sec->getOutputSection()->Addr + Sec->getOffset(Rel.r_offset);
 374     P->setSymbolAndType(InX::SymTab->getSymbolIndex(&Sym), Type,
 375                         Config->IsMips64EL);
 376
 377     if (Sym.Type == STT_SECTION) {
 378       // We combine multiple section symbols into only one per
 379       // section. This means we have to update the addend. That is
 380       // trivial for Elf_Rela, but for Elf_Rel we have to write to the
 381       // section data. We do that by adding to the Relocation vector.
 382
 383       // .eh_frame is horribly special and can reference discarded sections. To
 384       // avoid having to parse and recreate .eh_frame, we just replace any
 385       // relocation in it pointing to discarded sections with R_*_NONE, which
 386       // hopefully creates a frame that is ignored at runtime.
 387       auto *D = dyn_cast<Defined>(&Sym);
 388       if (!D) {
 389         error("STT_SECTION symbol should be defined");
 390         continue;
 391       }
 392       SectionBase *Section = D->Section;
 393       if (Section == &InputSection::Discarded) {
 394         P->setSymbolAndType(0, 0, false);
 395         continue;
 396       }
 397
 398       if (Config->IsRela) {
 399         P->r_addend =
 400             Sym.getVA(getAddend<ELFT>(Rel)) - Section->getOutputSection()->Addr;
 401       } else if (Config->Relocatable) {
 402         const uint8_t *BufLoc = Sec->Data.begin() + Rel.r_offset;
 403         Sec->Relocations.push_back({R_ABS, Type, Rel.r_offset,
 404                                     Target->getImplicitAddend(BufLoc, Type),
 405                                     &Sym});
 406       }
 407     }
 408
 409   }
 410 }
 411
 412 // The ARM and AArch64 ABI handle pc-relative relocations to undefined weak
 413 // references specially. The general rule is that the value of the symbol in
 414 // this context is the address of the place P. A further special case is that
 415 // branch relocations to an undefined weak reference resolve to the next
 416 // instruction.
 417 static uint32_t getARMUndefinedRelativeWeakVA(RelType Type, uint32_t A,
 418                                               uint32_t P) {
 419   switch (Type) {
 420   // Unresolved branch relocations to weak references resolve to next
 421   // instruction, this will be either 2 or 4 bytes on from P.
 422   case R_ARM_THM_JUMP11:
 423     return P + 2 + A;
 424   case R_ARM_CALL:
 425   case R_ARM_JUMP24:
 426   case R_ARM_PC24:
 427   case R_ARM_PLT32:
 428   case R_ARM_PREL31:
 429   case R_ARM_THM_JUMP19:
 430   case R_ARM_THM_JUMP24:
 431     return P + 4 + A;
 432   case R_ARM_THM_CALL:
 433     // We don't want an interworking BLX to ARM
 434     return P + 5 + A;
 435   // Unresolved non branch pc-relative relocations
 436   // R_ARM_TARGET2 which can be resolved relatively is not present as it never
 437   // targets a weak-reference.
 438   case R_ARM_MOVW_PREL_NC:
 439   case R_ARM_MOVT_PREL:
 440   case R_ARM_REL32:
 441   case R_ARM_THM_MOVW_PREL_NC:
 442   case R_ARM_THM_MOVT_PREL:
 443     return P + A;
 444   }
 445   llvm_unreachable("ARM pc-relative relocation expected\n");
 446 }
 447
 448 // The comment above getARMUndefinedRelativeWeakVA applies to this function.
 449 static uint64_t getAArch64UndefinedRelativeWeakVA(uint64_t Type, uint64_t A,
 450                                                   uint64_t P) {
 451   switch (Type) {
 452   // Unresolved branch relocations to weak references resolve to next
 453   // instruction, this is 4 bytes on from P.
 454   case R_AARCH64_CALL26:
 455   case R_AARCH64_CONDBR19:
 456   case R_AARCH64_JUMP26:
 457   case R_AARCH64_TSTBR14:
 458     return P + 4 + A;
 459   // Unresolved non branch pc-relative relocations
 460   case R_AARCH64_PREL16:
 461   case R_AARCH64_PREL32:
 462   case R_AARCH64_PREL64:
 463   case R_AARCH64_ADR_PREL_LO21:
 464   case R_AARCH64_LD_PREL_LO19:
 465     return P + A;
 466   }
 467   llvm_unreachable("AArch64 pc-relative relocation expected\n");
 468 }
 469
 470 // ARM SBREL relocations are of the form S + A - B where B is the static base
 471 // The ARM ABI defines base to be "addressing origin of the output segment
 472 // defining the symbol S". We defined the "addressing origin"/static base to be
 473 // the base of the PT_LOAD segment containing the Sym.
 474 // The procedure call standard only defines a Read Write Position Independent
 475 // RWPI variant so in practice we should expect the static base to be the base
 476 // of the RW segment.
 477 static uint64_t getARMStaticBase(const Symbol &Sym) {
 478   OutputSection *OS = Sym.getOutputSection();
 479   if (!OS || !OS->PtLoad || !OS->PtLoad->FirstSec)
 480     fatal("SBREL relocation to " + Sym.getName() + " without static base");
 481   return OS->PtLoad->FirstSec->Addr;
 482 }
 483
 484 static uint64_t getRelocTargetVA(RelType Type, int64_t A, uint64_t P,
 485                                  const Symbol &Sym, RelExpr Expr) {
 486   switch (Expr) {
 487   case R_INVALID:
 488     return 0;
 489   case R_ABS:
 490   case R_RELAX_GOT_PC_NOPIC:
 491     return Sym.getVA(A);
 492   case R_ARM_SBREL:
 493     return Sym.getVA(A) - getARMStaticBase(Sym);
 494   case R_GOT:
 495   case R_RELAX_TLS_GD_TO_IE_ABS:
 496     return Sym.getGotVA() + A;
 497   case R_GOTONLY_PC:
 498     return InX::Got->getVA() + A - P;
 499   case R_GOTONLY_PC_FROM_END:
 500     return InX::Got->getVA() + A - P + InX::Got->getSize();
 501   case R_GOTREL:
 502     return Sym.getVA(A) - InX::Got->getVA();
 503   case R_GOTREL_FROM_END:
 504     return Sym.getVA(A) - InX::Got->getVA() - InX::Got->getSize();
 505   case R_GOT_FROM_END:
 506   case R_RELAX_TLS_GD_TO_IE_END:
 507     return Sym.getGotOffset() + A - InX::Got->getSize();
 508   case R_GOT_OFF:
 509     return Sym.getGotOffset() + A;
 510   case R_GOT_PAGE_PC:
 511   case R_RELAX_TLS_GD_TO_IE_PAGE_PC:
 512     return getAArch64Page(Sym.getGotVA() + A) - getAArch64Page(P);
 513   case R_GOT_PC:
 514   case R_RELAX_TLS_GD_TO_IE:
 515     return Sym.getGotVA() + A - P;
 516   case R_HINT:
 517   case R_NONE:
 518   case R_TLSDESC_CALL:
 519     llvm_unreachable("cannot relocate hint relocs");
 520   case R_MIPS_GOTREL:
 521     return Sym.getVA(A) - InX::MipsGot->getGp();
 522   case R_MIPS_GOT_GP:
 523     return InX::MipsGot->getGp() + A;
 524   case R_MIPS_GOT_GP_PC: {
 525     // R_MIPS_LO16 expression has R_MIPS_GOT_GP_PC type iif the target
 526     // is _gp_disp symbol. In that case we should use the following
 527     // formula for calculation "AHL + GP - P + 4". For details see p. 4-19 at
 528     // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
 529     // microMIPS variants of these relocations use slightly different
 530     // expressions: AHL + GP - P + 3 for %lo() and AHL + GP - P - 1 for %hi()
 531     // to correctly handle less-sugnificant bit of the microMIPS symbol.
 532     uint64_t V = InX::MipsGot->getGp() + A - P;
 533     if (Type == R_MIPS_LO16 || Type == R_MICROMIPS_LO16)
 534       V += 4;
 535     if (Type == R_MICROMIPS_LO16 || Type == R_MICROMIPS_HI16)
 536       V -= 1;
 537     return V;
 538   }
 539   case R_MIPS_GOT_LOCAL_PAGE:
 540     // If relocation against MIPS local symbol requires GOT entry, this entry
 541     // should be initialized by 'page address'. This address is high 16-bits
 542     // of sum the symbol's value and the addend.
 543     return InX::MipsGot->getVA() + InX::MipsGot->getPageEntryOffset(Sym, A) -
 544            InX::MipsGot->getGp();
 545   case R_MIPS_GOT_OFF:
 546   case R_MIPS_GOT_OFF32:
 547     // In case of MIPS if a GOT relocation has non-zero addend this addend
 548     // should be applied to the GOT entry content not to the GOT entry offset.
 549     // That is why we use separate expression type.
 550     return InX::MipsGot->getVA() + InX::MipsGot->getSymEntryOffset(Sym, A) -
 551            InX::MipsGot->getGp();
 552   case R_MIPS_TLSGD:
 553     return InX::MipsGot->getVA() + InX::MipsGot->getTlsOffset() +
 554            InX::MipsGot->getGlobalDynOffset(Sym) - InX::MipsGot->getGp();
 555   case R_MIPS_TLSLD:
 556     return InX::MipsGot->getVA() + InX::MipsGot->getTlsOffset() +
 557            InX::MipsGot->getTlsIndexOff() - InX::MipsGot->getGp();
 558   case R_PAGE_PC:
 559   case R_PLT_PAGE_PC: {
 560     uint64_t Dest;
 561     if (Sym.isUndefWeak())
 562       Dest = getAArch64Page(A);
 563     else
 564       Dest = getAArch64Page(Sym.getVA(A));
 565     return Dest - getAArch64Page(P);
 566   }
 567   case R_PC: {
 568     uint64_t Dest;
 569     if (Sym.isUndefWeak()) {
 570       // On ARM and AArch64 a branch to an undefined weak resolves to the
 571       // next instruction, otherwise the place.
 572       if (Config->EMachine == EM_ARM)
 573         Dest = getARMUndefinedRelativeWeakVA(Type, A, P);
 574       else if (Config->EMachine == EM_AARCH64)
 575         Dest = getAArch64UndefinedRelativeWeakVA(Type, A, P);
 576       else
 577         Dest = Sym.getVA(A);
 578     } else {
 579       Dest = Sym.getVA(A);
 580     }
 581     return Dest - P;
 582   }
 583   case R_PLT:
 584     return Sym.getPltVA() + A;
 585   case R_PLT_PC:
 586   case R_PPC_PLT_OPD:
 587     return Sym.getPltVA() + A - P;
 588   case R_PPC_OPD: {
 589     uint64_t SymVA = Sym.getVA(A);
 590     // If we have an undefined weak symbol, we might get here with a symbol
 591     // address of zero. That could overflow, but the code must be unreachable,
 592     // so don't bother doing anything at all.
 593     if (!SymVA)
 594       return 0;
 595     if (Out::Opd) {
 596       // If this is a local call, and we currently have the address of a
 597       // function-descriptor, get the underlying code address instead.
 598       uint64_t OpdStart = Out::Opd->Addr;
 599       uint64_t OpdEnd = OpdStart + Out::Opd->Size;
 600       bool InOpd = OpdStart <= SymVA && SymVA < OpdEnd;
 601       if (InOpd)
 602         SymVA = read64be(&Out::OpdBuf[SymVA - OpdStart]);
 603     }
 604     return SymVA - P;
 605   }
 606   case R_PPC_TOC:
 607     return getPPC64TocBase() + A;
 608   case R_RELAX_GOT_PC:
 609     return Sym.getVA(A) - P;
 610   case R_RELAX_TLS_GD_TO_LE:
 611   case R_RELAX_TLS_IE_TO_LE:
 612   case R_RELAX_TLS_LD_TO_LE:
 613   case R_TLS:
 614     // A weak undefined TLS symbol resolves to the base of the TLS
 615     // block, i.e. gets a value of zero. If we pass --gc-sections to
 616     // lld and .tbss is not referenced, it gets reclaimed and we don't
 617     // create a TLS program header. Therefore, we resolve this
 618     // statically to zero.
 619     if (Sym.isTls() && Sym.isUndefWeak())
 620       return 0;
 621     if (Target->TcbSize)
 622       return Sym.getVA(A) + alignTo(Target->TcbSize, Out::TlsPhdr->p_align);
 623     return Sym.getVA(A) - Out::TlsPhdr->p_memsz;
 624   case R_RELAX_TLS_GD_TO_LE_NEG:
 625   case R_NEG_TLS:
 626     return Out::TlsPhdr->p_memsz - Sym.getVA(A);
 627   case R_SIZE:
 628     return A; // Sym.getSize was already folded into the addend.
 629   case R_TLSDESC:
 630     return InX::Got->getGlobalDynAddr(Sym) + A;
 631   case R_TLSDESC_PAGE:
 632     return getAArch64Page(InX::Got->getGlobalDynAddr(Sym) + A) -
 633            getAArch64Page(P);
 634   case R_TLSGD:
 635     return InX::Got->getGlobalDynOffset(Sym) + A - InX::Got->getSize();
 636   case R_TLSGD_PC:
 637     return InX::Got->getGlobalDynAddr(Sym) + A - P;
 638   case R_TLSLD:
 639     return InX::Got->getTlsIndexOff() + A - InX::Got->getSize();
 640   case R_TLSLD_PC:
 641     return InX::Got->getTlsIndexVA() + A - P;
 642   }
 643   llvm_unreachable("Invalid expression");
 644 }
 645
 646 // This function applies relocations to sections without SHF_ALLOC bit.
 647 // Such sections are never mapped to memory at runtime. Debug sections are
 648 // an example. Relocations in non-alloc sections are much easier to
 649 // handle than in allocated sections because it will never need complex
 650 // treatement such as GOT or PLT (because at runtime no one refers them).
 651 // So, we handle relocations for non-alloc sections directly in this
 652 // function as a performance optimization.
 653 template <class ELFT, class RelTy>
 654 void InputSection::relocateNonAlloc(uint8_t *Buf, ArrayRef<RelTy> Rels) {
 655   const unsigned Bits = sizeof(typename ELFT::uint) * 8;
 656
 657   for (const RelTy &Rel : Rels) {
 658     RelType Type = Rel.getType(Config->IsMips64EL);
 659     uint64_t Offset = getOffset(Rel.r_offset);
 660     uint8_t *BufLoc = Buf + Offset;
 661     int64_t Addend = getAddend<ELFT>(Rel);
 662     if (!RelTy::IsRela)
 663       Addend += Target->getImplicitAddend(BufLoc, Type);
 664
 665     Symbol &Sym = getFile<ELFT>()->getRelocTargetSym(Rel);
 666     RelExpr Expr = Target->getRelExpr(Type, Sym, BufLoc);
 667     if (Expr == R_NONE)
 668       continue;
 669     if (Expr != R_ABS) {
 670       // GCC 8.0 or earlier have a bug that it emits R_386_GOTPC relocations
 671       // against _GLOBAL_OFFSET_TABLE for .debug_info. The bug seems to have
 672       // been fixed in 2017: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82630,
 673       // but we need to keep this bug-compatible code for a while.
 674       if (Config->EMachine == EM_386 && Type == R_386_GOTPC)
 675         continue;
 676
 677       error(getLocation<ELFT>(Offset) + ": has non-ABS relocation " +
 678             toString(Type) + " against symbol '" + toString(Sym) + "'");
 679       return;
 680     }
 681
 682     if (Sym.isTls() && !Out::TlsPhdr)
 683       Target->relocateOne(BufLoc, Type, 0);
 684     else
 685       Target->relocateOne(BufLoc, Type, SignExtend64<Bits>(Sym.getVA(Addend)));
 686   }
 687 }
 688
 689 // This is used when '-r' is given.
 690 // For REL targets, InputSection::copyRelocations() may store artificial
 691 // relocations aimed to update addends. They are handled in relocateAlloc()
 692 // for allocatable sections, and this function does the same for
 693 // non-allocatable sections, such as sections with debug information.
 694 static void relocateNonAllocForRelocatable(InputSection *Sec, uint8_t *Buf) {
 695   const unsigned Bits = Config->Is64 ? 64 : 32;
 696
 697   for (const Relocation &Rel : Sec->Relocations) {
 698     // InputSection::copyRelocations() adds only R_ABS relocations.
 699     assert(Rel.Expr == R_ABS);
 700     uint8_t *BufLoc = Buf + Rel.Offset + Sec->OutSecOff;
 701     uint64_t TargetVA = SignExtend64(Rel.Sym->getVA(Rel.Addend), Bits);
 702     Target->relocateOne(BufLoc, Rel.Type, TargetVA);
 703   }
 704 }
 705
 706 template <class ELFT>
 707 void InputSectionBase::relocate(uint8_t *Buf, uint8_t *BufEnd) {
 708   if (Flags & SHF_ALLOC) {
 709     relocateAlloc(Buf, BufEnd);
 710     return;
 711   }
 712
 713   auto *Sec = cast<InputSection>(this);
 714   if (Config->Relocatable)
 715     relocateNonAllocForRelocatable(Sec, Buf);
 716   else if (Sec->AreRelocsRela)
 717     Sec->relocateNonAlloc<ELFT>(Buf, Sec->template relas<ELFT>());
 718   else
 719     Sec->relocateNonAlloc<ELFT>(Buf, Sec->template rels<ELFT>());
 720 }
 721
 722 void InputSectionBase::relocateAlloc(uint8_t *Buf, uint8_t *BufEnd) {
 723   assert(Flags & SHF_ALLOC);
 724   const unsigned Bits = Config->Wordsize * 8;
 725
 726   for (const Relocation &Rel : Relocations) {
 727     uint64_t Offset = getOffset(Rel.Offset);
 728     uint8_t *BufLoc = Buf + Offset;
 729     RelType Type = Rel.Type;
 730
 731     uint64_t AddrLoc = getOutputSection()->Addr + Offset;
 732     RelExpr Expr = Rel.Expr;
 733     uint64_t TargetVA = SignExtend64(
 734         getRelocTargetVA(Type, Rel.Addend, AddrLoc, *Rel.Sym, Expr), Bits);
 735
 736     switch (Expr) {
 737     case R_RELAX_GOT_PC:
 738     case R_RELAX_GOT_PC_NOPIC:
 739       Target->relaxGot(BufLoc, TargetVA);
 740       break;
 741     case R_RELAX_TLS_IE_TO_LE:
 742       Target->relaxTlsIeToLe(BufLoc, Type, TargetVA);
 743       break;
 744     case R_RELAX_TLS_LD_TO_LE:
 745       Target->relaxTlsLdToLe(BufLoc, Type, TargetVA);
 746       break;
 747     case R_RELAX_TLS_GD_TO_LE:
 748     case R_RELAX_TLS_GD_TO_LE_NEG:
 749       Target->relaxTlsGdToLe(BufLoc, Type, TargetVA);
 750       break;
 751     case R_RELAX_TLS_GD_TO_IE:
 752     case R_RELAX_TLS_GD_TO_IE_ABS:
 753     case R_RELAX_TLS_GD_TO_IE_PAGE_PC:
 754     case R_RELAX_TLS_GD_TO_IE_END:
 755       Target->relaxTlsGdToIe(BufLoc, Type, TargetVA);
 756       break;
 757     case R_PPC_PLT_OPD:
 758       // Patch a nop (0x60000000) to a ld.
 759       if (BufLoc + 8 <= BufEnd && read32be(BufLoc + 4) == 0x60000000)
 760         write32be(BufLoc + 4, 0xe8410028); // ld %r2, 40(%r1)
 761       LLVM_FALLTHROUGH;
 762     default:
 763       Target->relocateOne(BufLoc, Type, TargetVA);
 764       break;
 765     }
 766   }
 767 }
 768
 769 template <class ELFT> void InputSection::writeTo(uint8_t *Buf) {
 770   if (Type == SHT_NOBITS)
 771     return;
 772
 773   if (auto *S = dyn_cast<SyntheticSection>(this)) {
 774     S->writeTo(Buf + OutSecOff);
 775     return;
 776   }
 777
 778   // If -r or --emit-relocs is given, then an InputSection
 779   // may be a relocation section.
 780   if (Type == SHT_RELA) {
 781     copyRelocations<ELFT>(Buf + OutSecOff, getDataAs<typename ELFT::Rela>());
 782     return;
 783   }
 784   if (Type == SHT_REL) {
 785     copyRelocations<ELFT>(Buf + OutSecOff, getDataAs<typename ELFT::Rel>());
 786     return;
 787   }
 788
 789   // If -r is given, we may have a SHT_GROUP section.
 790   if (Type == SHT_GROUP) {
 791     copyShtGroup<ELFT>(Buf + OutSecOff);
 792     return;
 793   }
 794
 795   // Copy section contents from source object file to output file
 796   // and then apply relocations.
 797   memcpy(Buf + OutSecOff, Data.data(), Data.size());
 798   uint8_t *BufEnd = Buf + OutSecOff + Data.size();
 799   relocate<ELFT>(Buf, BufEnd);
 800 }
 801
 802 void InputSection::replace(InputSection *Other) {
 803   Alignment = std::max(Alignment, Other->Alignment);
 804   Other->Repl = Repl;
 805   Other->Live = false;
 806 }
 807
 808 template <class ELFT>
 809 EhInputSection::EhInputSection(ObjFile<ELFT> &F,
 810                                const typename ELFT::Shdr &Header,
 811                                StringRef Name)
 812     : InputSectionBase(F, Header, Name, InputSectionBase::EHFrame) {}
 813
 814 SyntheticSection *EhInputSection::getParent() const {
 815   return cast_or_null<SyntheticSection>(Parent);
 816 }
 817
 818 // Returns the index of the first relocation that points to a region between
 819 // Begin and Begin+Size.
 820 template <class IntTy, class RelTy>
 821 static unsigned getReloc(IntTy Begin, IntTy Size, const ArrayRef<RelTy> &Rels,
 822                          unsigned &RelocI) {
 823   // Start search from RelocI for fast access. That works because the
 824   // relocations are sorted in .eh_frame.
 825   for (unsigned N = Rels.size(); RelocI < N; ++RelocI) {
 826     const RelTy &Rel = Rels[RelocI];
 827     if (Rel.r_offset < Begin)
 828       continue;
 829
 830     if (Rel.r_offset < Begin + Size)
 831       return RelocI;
 832     return -1;
 833   }
 834   return -1;
 835 }
 836
 837 // .eh_frame is a sequence of CIE or FDE records.
 838 // This function splits an input section into records and returns them.
 839 template <class ELFT> void EhInputSection::split() {
 840   // Early exit if already split.
 841   if (!Pieces.empty())
 842     return;
 843
 844   if (AreRelocsRela)
 845     split<ELFT>(relas<ELFT>());
 846   else
 847     split<ELFT>(rels<ELFT>());
 848 }
 849
 850 template <class ELFT, class RelTy>
 851 void EhInputSection::split(ArrayRef<RelTy> Rels) {
 852   unsigned RelI = 0;
 853   for (size_t Off = 0, End = Data.size(); Off != End;) {
 854     size_t Size = readEhRecordSize(this, Off);
 855     Pieces.emplace_back(Off, this, Size, getReloc(Off, Size, Rels, RelI));
 856     // The empty record is the end marker.
 857     if (Size == 4)
 858       break;
 859     Off += Size;
 860   }
 861 }
 862
 863 static size_t findNull(StringRef S, size_t EntSize) {
 864   // Optimize the common case.
 865   if (EntSize == 1)
 866     return S.find(0);
 867
 868   for (unsigned I = 0, N = S.size(); I != N; I += EntSize) {
 869     const char *B = S.begin() + I;
 870     if (std::all_of(B, B + EntSize, [](char C) { return C == 0; }))
 871       return I;
 872   }
 873   return StringRef::npos;
 874 }
 875
 876 SyntheticSection *MergeInputSection::getParent() const {
 877   return cast_or_null<SyntheticSection>(Parent);
 878 }
 879
 880 // Split SHF_STRINGS section. Such section is a sequence of
 881 // null-terminated strings.
 882 void MergeInputSection::splitStrings(ArrayRef<uint8_t> Data, size_t EntSize) {
 883   size_t Off = 0;
 884   bool IsAlloc = Flags & SHF_ALLOC;
 885   StringRef S = toStringRef(Data);
 886
 887   while (!S.empty()) {
 888     size_t End = findNull(S, EntSize);
 889     if (End == StringRef::npos)
 890       fatal(toString(this) + ": string is not null terminated");
 891     size_t Size = End + EntSize;
 892
 893     Pieces.emplace_back(Off, xxHash64(S.substr(0, Size)), !IsAlloc);
 894     S = S.substr(Size);
 895     Off += Size;
 896   }
 897 }
 898
 899 // Split non-SHF_STRINGS section. Such section is a sequence of
 900 // fixed size records.
 901 void MergeInputSection::splitNonStrings(ArrayRef<uint8_t> Data,
 902                                         size_t EntSize) {
 903   size_t Size = Data.size();
 904   assert((Size % EntSize) == 0);
 905   bool IsAlloc = Flags & SHF_ALLOC;
 906
 907   for (size_t I = 0; I != Size; I += EntSize)
 908     Pieces.emplace_back(I, xxHash64(toStringRef(Data.slice(I, EntSize))),
 909                         !IsAlloc);
 910 }
 911
 912 template <class ELFT>
 913 MergeInputSection::MergeInputSection(ObjFile<ELFT> &F,
 914                                      const typename ELFT::Shdr &Header,
 915                                      StringRef Name)
 916     : InputSectionBase(F, Header, Name, InputSectionBase::Merge) {}
 917
 918 MergeInputSection::MergeInputSection(uint64_t Flags, uint32_t Type,
 919                                      uint64_t Entsize, ArrayRef<uint8_t> Data,
 920                                      StringRef Name)
 921     : InputSectionBase(nullptr, Flags, Type, Entsize, /*Link*/ 0, /*Info*/ 0,
 922                        /*Alignment*/ Entsize, Data, Name, SectionBase::Merge) {}
 923
 924 // This function is called after we obtain a complete list of input sections
 925 // that need to be linked. This is responsible to split section contents
 926 // into small chunks for further processing.
 927 //
 928 // Note that this function is called from parallelForEach. This must be
 929 // thread-safe (i.e. no memory allocation from the pools).
 930 void MergeInputSection::splitIntoPieces() {
 931   assert(Pieces.empty());
 932
 933   if (Flags & SHF_STRINGS)
 934     splitStrings(Data, Entsize);
 935   else
 936     splitNonStrings(Data, Entsize);
 937
 938   if (Config->GcSections && (Flags & SHF_ALLOC))
 939     for (uint64_t Off : LiveOffsets)
 940       getSectionPiece(Off)->Live = true;
 941 }
 942
 943 // Do binary search to get a section piece at a given input offset.
 944 SectionPiece *MergeInputSection::getSectionPiece(uint64_t Offset) {
 945   auto *This = static_cast<const MergeInputSection *>(this);
 946   return const_cast<SectionPiece *>(This->getSectionPiece(Offset));
 947 }
 948
 949 template <class It, class T, class Compare>
 950 static It fastUpperBound(It First, It Last, const T &Value, Compare Comp) {
 951   size_t Size = std::distance(First, Last);
 952   assert(Size != 0);
 953   while (Size != 1) {
 954     size_t H = Size / 2;
 955     const It MI = First + H;
 956     Size -= H;
 957     First = Comp(Value, *MI) ? First : First + H;
 958   }
 959   return Comp(Value, *First) ? First : First + 1;
 960 }
 961
 962 const SectionPiece *MergeInputSection::getSectionPiece(uint64_t Offset) const {
 963   if (Data.size() <= Offset)
 964     fatal(toString(this) + ": entry is past the end of the section");
 965
 966   // Find the element this offset points to.
 967   auto I = fastUpperBound(
 968       Pieces.begin(), Pieces.end(), Offset,
 969       [](const uint64_t &A, const SectionPiece &B) { return A < B.InputOff; });
 970   --I;
 971   return &*I;
 972 }
 973
 974 // Returns the offset in an output section for a given input offset.
 975 // Because contents of a mergeable section is not contiguous in output,
 976 // it is not just an addition to a base output offset.
 977 uint64_t MergeInputSection::getOffset(uint64_t Offset) const {
 978   if (!Live)
 979     return 0;
 980
 981   // Initialize OffsetMap lazily.
 982   llvm::call_once(InitOffsetMap, [&] {
 983     OffsetMap.reserve(Pieces.size());
 984     for (size_t I = 0; I < Pieces.size(); ++I)
 985       OffsetMap[Pieces[I].InputOff] = I;
 986   });
 987
 988   // Find a string starting at a given offset.
 989   auto It = OffsetMap.find(Offset);
 990   if (It != OffsetMap.end())
 991     return Pieces[It->second].OutputOff;
 992
 993   // If Offset is not at beginning of a section piece, it is not in the map.
 994   // In that case we need to search from the original section piece vector.
 995   const SectionPiece &Piece = *getSectionPiece(Offset);
 996   if (!Piece.Live)
 997     return 0;
 998
 999   uint64_t Addend = Offset - Piece.InputOff;
1000   return Piece.OutputOff + Addend;
1001 }
1002
1003 template InputSection::InputSection(ObjFile<ELF32LE> &, const ELF32LE::Shdr &,
1004                                     StringRef);
1005 template InputSection::InputSection(ObjFile<ELF32BE> &, const ELF32BE::Shdr &,
1006                                     StringRef);
1007 template InputSection::InputSection(ObjFile<ELF64LE> &, const ELF64LE::Shdr &,
1008                                     StringRef);
1009 template InputSection::InputSection(ObjFile<ELF64BE> &, const ELF64BE::Shdr &,
1010                                     StringRef);
1011
1012 template std::string InputSectionBase::getLocation<ELF32LE>(uint64_t);
1013 template std::string InputSectionBase::getLocation<ELF32BE>(uint64_t);
1014 template std::string InputSectionBase::getLocation<ELF64LE>(uint64_t);
1015 template std::string InputSectionBase::getLocation<ELF64BE>(uint64_t);
1016
1017 template void InputSection::writeTo<ELF32LE>(uint8_t *);
1018 template void InputSection::writeTo<ELF32BE>(uint8_t *);
1019 template void InputSection::writeTo<ELF64LE>(uint8_t *);
1020 template void InputSection::writeTo<ELF64BE>(uint8_t *);
1021
1022 template MergeInputSection::MergeInputSection(ObjFile<ELF32LE> &,
1023                                               const ELF32LE::Shdr &, StringRef);
1024 template MergeInputSection::MergeInputSection(ObjFile<ELF32BE> &,
1025                                               const ELF32BE::Shdr &, StringRef);
1026 template MergeInputSection::MergeInputSection(ObjFile<ELF64LE> &,
1027                                               const ELF64LE::Shdr &, StringRef);
1028 template MergeInputSection::MergeInputSection(ObjFile<ELF64BE> &,
1029                                               const ELF64BE::Shdr &, StringRef);
1030
1031 template EhInputSection::EhInputSection(ObjFile<ELF32LE> &,
1032                                         const ELF32LE::Shdr &, StringRef);
1033 template EhInputSection::EhInputSection(ObjFile<ELF32BE> &,
1034                                         const ELF32BE::Shdr &, StringRef);
1035 template EhInputSection::EhInputSection(ObjFile<ELF64LE> &,
1036                                         const ELF64LE::Shdr &, StringRef);
1037 template EhInputSection::EhInputSection(ObjFile<ELF64BE> &,
1038                                         const ELF64BE::Shdr &, StringRef);
1039
1040 template void EhInputSection::split<ELF32LE>();
1041 template void EhInputSection::split<ELF32BE>();
1042 template void EhInputSection::split<ELF64LE>();
1043 template void EhInputSection::split<ELF64BE>();