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