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 "SymbolTable.h"
  18 #include "Symbols.h"
  19 #include "SyntheticSections.h"
  20 #include "Target.h"
  21 #include "Thunks.h"
  22 #include "lld/Common/ErrorHandler.h"
  23 #include "lld/Common/Memory.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 <algorithm>
  30 #include <mutex>
  31 #include <set>
  32 #include <vector>
  33
  34 using namespace llvm;
  35 using namespace llvm::ELF;
  36 using namespace llvm::object;
  37 using namespace llvm::support;
  38 using namespace llvm::support::endian;
  39 using namespace llvm::sys;
  40
  41 using namespace lld;
  42 using namespace lld::elf;
  43
  44 std::vector<InputSectionBase *> elf::InputSections;
  45
  46 // Returns a string to construct an error message.
  47 std::string lld::toString(const InputSectionBase *Sec) {
  48   return (toString(Sec->File) + ":(" + Sec->Name + ")").str();
  49 }
  50
  51 template <class ELFT>
  52 static ArrayRef<uint8_t> getSectionContents(ObjFile<ELFT> &File,
  53                                             const typename ELFT::Shdr &Hdr) {
  54   if (Hdr.sh_type == SHT_NOBITS)
  55     return makeArrayRef<uint8_t>(nullptr, Hdr.sh_size);
  56   return check(File.getObj().getSectionContents(&Hdr));
  57 }
  58
  59 InputSectionBase::InputSectionBase(InputFile *File, uint64_t Flags,
  60                                    uint32_t Type, uint64_t Entsize,
  61                                    uint32_t Link, uint32_t Info,
  62                                    uint32_t Alignment, ArrayRef<uint8_t> Data,
  63                                    StringRef Name, Kind SectionKind)
  64     : SectionBase(SectionKind, Name, Flags, Entsize, Alignment, Type, Info,
  65                   Link),
  66       File(File), RawData(Data) {
  67   // In order to reduce memory allocation, we assume that mergeable
  68   // sections are smaller than 4 GiB, which is not an unreasonable
  69   // assumption as of 2017.
  70   if (SectionKind == SectionBase::Merge && RawData.size() > UINT32_MAX)
  71     error(toString(this) + ": section too large");
  72
  73   NumRelocations = 0;
  74   AreRelocsRela = false;
  75
  76   // The ELF spec states that a value of 0 means the section has
  77   // no alignment constraits.
  78   uint32_t V = std::max<uint64_t>(Alignment, 1);
  79   if (!isPowerOf2_64(V))
  80     fatal(toString(File) + ": section sh_addralign is not a power of 2");
  81   this->Alignment = V;
  82
  83   // In ELF, each section can be compressed by zlib, and if compressed,
  84   // section name may be mangled by appending "z" (e.g. ".zdebug_info").
  85   // If that's the case, demangle section name so that we can handle a
  86   // section as if it weren't compressed.
  87   if ((Flags & SHF_COMPRESSED) || Name.startswith(".zdebug")) {
  88     if (!zlib::isAvailable())
  89       error(toString(File) + ": contains a compressed section, " +
  90             "but zlib is not available");
  91     parseCompressedHeader();
  92   }
  93 }
  94
  95 // Drop SHF_GROUP bit unless we are producing a re-linkable object file.
  96 // SHF_GROUP is a marker that a section belongs to some comdat group.
  97 // That flag doesn't make sense in an executable.
  98 static uint64_t getFlags(uint64_t Flags) {
  99   Flags &= ~(uint64_t)SHF_INFO_LINK;
 100   if (!Config->Relocatable)
 101     Flags &= ~(uint64_t)SHF_GROUP;
 102   return Flags;
 103 }
 104
 105 // GNU assembler 2.24 and LLVM 4.0.0's MC (the newest release as of
 106 // March 2017) fail to infer section types for sections starting with
 107 // ".init_array." or ".fini_array.". They set SHT_PROGBITS instead of
 108 // SHF_INIT_ARRAY. As a result, the following assembler directive
 109 // creates ".init_array.100" with SHT_PROGBITS, for example.
 110 //
 111 //   .section .init_array.100, "aw"
 112 //
 113 // This function forces SHT_{INIT,FINI}_ARRAY so that we can handle
 114 // incorrect inputs as if they were correct from the beginning.
 115 static uint64_t getType(uint64_t Type, StringRef Name) {
 116   if (Type == SHT_PROGBITS && Name.startswith(".init_array."))
 117     return SHT_INIT_ARRAY;
 118   if (Type == SHT_PROGBITS && Name.startswith(".fini_array."))
 119     return SHT_FINI_ARRAY;
 120   return Type;
 121 }
 122
 123 template <class ELFT>
 124 InputSectionBase::InputSectionBase(ObjFile<ELFT> &File,
 125                                    const typename ELFT::Shdr &Hdr,
 126                                    StringRef Name, Kind SectionKind)
 127     : InputSectionBase(&File, getFlags(Hdr.sh_flags),
 128                        getType(Hdr.sh_type, Name), Hdr.sh_entsize, Hdr.sh_link,
 129                        Hdr.sh_info, Hdr.sh_addralign,
 130                        getSectionContents(File, Hdr), Name, SectionKind) {
 131   // We reject object files having insanely large alignments even though
 132   // they are allowed by the spec. I think 4GB is a reasonable limitation.
 133   // We might want to relax this in the future.
 134   if (Hdr.sh_addralign > UINT32_MAX)
 135     fatal(toString(&File) + ": section sh_addralign is too large");
 136 }
 137
 138 size_t InputSectionBase::getSize() const {
 139   if (auto *S = dyn_cast<SyntheticSection>(this))
 140     return S->getSize();
 141   if (UncompressedSize >= 0)
 142     return UncompressedSize;
 143   return RawData.size();
 144 }
 145
 146 void InputSectionBase::uncompress() const {
 147   size_t Size = UncompressedSize;
 148   UncompressedBuf.reset(new char[Size]);
 149
 150   if (Error E =
 151           zlib::uncompress(toStringRef(RawData), UncompressedBuf.get(), Size))
 152     fatal(toString(this) +
 153           ": uncompress failed: " + llvm::toString(std::move(E)));
 154   RawData = makeArrayRef((uint8_t *)UncompressedBuf.get(), 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   case Synthetic:
 172     return cast<InputSection>(this)->getOffset(Offset);
 173   case EHFrame:
 174     // The file crtbeginT.o has relocations pointing to the start of an empty
 175     // .eh_frame that is known to be the first in the link. It does that to
 176     // identify the start of the output .eh_frame.
 177     return Offset;
 178   case Merge:
 179     const MergeInputSection *MS = cast<MergeInputSection>(this);
 180     if (InputSection *IS = MS->getParent())
 181       return IS->getOffset(MS->getParentOffset(Offset));
 182     return MS->getParentOffset(Offset);
 183   }
 184   llvm_unreachable("invalid section kind");
 185 }
 186
 187 uint64_t SectionBase::getVA(uint64_t Offset) const {
 188   const OutputSection *Out = getOutputSection();
 189   return (Out ? Out->Addr : 0) + getOffset(Offset);
 190 }
 191
 192 OutputSection *SectionBase::getOutputSection() {
 193   InputSection *Sec;
 194   if (auto *IS = dyn_cast<InputSection>(this))
 195     Sec = IS;
 196   else if (auto *MS = dyn_cast<MergeInputSection>(this))
 197     Sec = MS->getParent();
 198   else if (auto *EH = dyn_cast<EhInputSection>(this))
 199     Sec = EH->getParent();
 200   else
 201     return cast<OutputSection>(this);
 202   return Sec ? Sec->getParent() : nullptr;
 203 }
 204
 205 // When a section is compressed, `RawData` consists with a header followed
 206 // by zlib-compressed data. This function parses a header to initialize
 207 // `UncompressedSize` member and remove the header from `RawData`.
 208 void InputSectionBase::parseCompressedHeader() {
 209   typedef typename ELF64LE::Chdr Chdr64;
 210   typedef typename ELF32LE::Chdr Chdr32;
 211
 212   // Old-style header
 213   if (Name.startswith(".zdebug")) {
 214     if (!toStringRef(RawData).startswith("ZLIB")) {
 215       error(toString(this) + ": corrupted compressed section header");
 216       return;
 217     }
 218     RawData = RawData.slice(4);
 219
 220     if (RawData.size() < 8) {
 221       error(toString(this) + ": corrupted compressed section header");
 222       return;
 223     }
 224
 225     UncompressedSize = read64be(RawData.data());
 226     RawData = RawData.slice(8);
 227
 228     // Restore the original section name.
 229     // (e.g. ".zdebug_info" -> ".debug_info")
 230     Name = Saver.save("." + Name.substr(2));
 231     return;
 232   }
 233
 234   assert(Flags & SHF_COMPRESSED);
 235   Flags &= ~(uint64_t)SHF_COMPRESSED;
 236
 237   // New-style 64-bit header
 238   if (Config->Is64) {
 239     if (RawData.size() < sizeof(Chdr64)) {
 240       error(toString(this) + ": corrupted compressed section");
 241       return;
 242     }
 243
 244     auto *Hdr = reinterpret_cast<const Chdr64 *>(RawData.data());
 245     if (Hdr->ch_type != ELFCOMPRESS_ZLIB) {
 246       error(toString(this) + ": unsupported compression type");
 247       return;
 248     }
 249
 250     UncompressedSize = Hdr->ch_size;
 251     RawData = RawData.slice(sizeof(*Hdr));
 252     return;
 253   }
 254
 255   // New-style 32-bit header
 256   if (RawData.size() < sizeof(Chdr32)) {
 257     error(toString(this) + ": corrupted compressed section");
 258     return;
 259   }
 260
 261   auto *Hdr = reinterpret_cast<const Chdr32 *>(RawData.data());
 262   if (Hdr->ch_type != ELFCOMPRESS_ZLIB) {
 263     error(toString(this) + ": unsupported compression type");
 264     return;
 265   }
 266
 267   UncompressedSize = Hdr->ch_size;
 268   RawData = RawData.slice(sizeof(*Hdr));
 269 }
 270
 271 InputSection *InputSectionBase::getLinkOrderDep() const {
 272   assert(Link);
 273   assert(Flags & SHF_LINK_ORDER);
 274   return cast<InputSection>(File->getSections()[Link]);
 275 }
 276
 277 // Find a function symbol that encloses a given location.
 278 template <class ELFT>
 279 Defined *InputSectionBase::getEnclosingFunction(uint64_t Offset) {
 280   for (Symbol *B : File->getSymbols())
 281     if (Defined *D = dyn_cast<Defined>(B))
 282       if (D->Section == this && D->Type == STT_FUNC && D->Value <= Offset &&
 283           Offset < D->Value + D->Size)
 284         return D;
 285   return nullptr;
 286 }
 287
 288 // Returns a source location string. Used to construct an error message.
 289 template <class ELFT>
 290 std::string InputSectionBase::getLocation(uint64_t Offset) {
 291   std::string SecAndOffset = (Name + "+0x" + utohexstr(Offset)).str();
 292
 293   // We don't have file for synthetic sections.
 294   if (getFile<ELFT>() == nullptr)
 295     return (Config->OutputFile + ":(" + SecAndOffset + ")")
 296         .str();
 297
 298   // First check if we can get desired values from debugging information.
 299   if (Optional<DILineInfo> Info = getFile<ELFT>()->getDILineInfo(this, Offset))
 300     return Info->FileName + ":" + std::to_string(Info->Line) + ":(" +
 301            SecAndOffset + ")";
 302
 303   // File->SourceFile contains STT_FILE symbol that contains a
 304   // source file name. If it's missing, we use an object file name.
 305   std::string SrcFile = getFile<ELFT>()->SourceFile;
 306   if (SrcFile.empty())
 307     SrcFile = toString(File);
 308
 309   if (Defined *D = getEnclosingFunction<ELFT>(Offset))
 310     return SrcFile + ":(function " + toString(*D) + ": " + SecAndOffset + ")";
 311
 312   // If there's no symbol, print out the offset in the section.
 313   return (SrcFile + ":(" + SecAndOffset + ")");
 314 }
 315
 316 // This function is intended to be used for constructing an error message.
 317 // The returned message looks like this:
 318 //
 319 //   foo.c:42 (/home/alice/possibly/very/long/path/foo.c:42)
 320 //
 321 //  Returns an empty string if there's no way to get line info.
 322 std::string InputSectionBase::getSrcMsg(const Symbol &Sym, uint64_t Offset) {
 323   return File->getSrcMsg(Sym, *this, Offset);
 324 }
 325
 326 // Returns a filename string along with an optional section name. This
 327 // function is intended to be used for constructing an error
 328 // message. The returned message looks like this:
 329 //
 330 //   path/to/foo.o:(function bar)
 331 //
 332 // or
 333 //
 334 //   path/to/foo.o:(function bar) in archive path/to/bar.a
 335 std::string InputSectionBase::getObjMsg(uint64_t Off) {
 336   std::string Filename = File->getName();
 337
 338   std::string Archive;
 339   if (!File->ArchiveName.empty())
 340     Archive = " in archive " + File->ArchiveName;
 341
 342   // Find a symbol that encloses a given location.
 343   for (Symbol *B : File->getSymbols())
 344     if (auto *D = dyn_cast<Defined>(B))
 345       if (D->Section == this && D->Value <= Off && Off < D->Value + D->Size)
 346         return Filename + ":(" + toString(*D) + ")" + Archive;
 347
 348   // If there's no symbol, print out the offset in the section.
 349   return (Filename + ":(" + Name + "+0x" + utohexstr(Off) + ")" + Archive)
 350       .str();
 351 }
 352
 353 InputSection InputSection::Discarded(nullptr, 0, 0, 0, ArrayRef<uint8_t>(), "");
 354
 355 InputSection::InputSection(InputFile *F, uint64_t Flags, uint32_t Type,
 356                            uint32_t Alignment, ArrayRef<uint8_t> Data,
 357                            StringRef Name, Kind K)
 358     : InputSectionBase(F, Flags, Type,
 359                        /*Entsize*/ 0, /*Link*/ 0, /*Info*/ 0, Alignment, Data,
 360                        Name, K) {}
 361
 362 template <class ELFT>
 363 InputSection::InputSection(ObjFile<ELFT> &F, const typename ELFT::Shdr &Header,
 364                            StringRef Name)
 365     : InputSectionBase(F, Header, Name, InputSectionBase::Regular) {}
 366
 367 bool InputSection::classof(const SectionBase *S) {
 368   return S->kind() == SectionBase::Regular ||
 369          S->kind() == SectionBase::Synthetic;
 370 }
 371
 372 OutputSection *InputSection::getParent() const {
 373   return cast_or_null<OutputSection>(Parent);
 374 }
 375
 376 // Copy SHT_GROUP section contents. Used only for the -r option.
 377 template <class ELFT> void InputSection::copyShtGroup(uint8_t *Buf) {
 378   // ELFT::Word is the 32-bit integral type in the target endianness.
 379   typedef typename ELFT::Word u32;
 380   ArrayRef<u32> From = getDataAs<u32>();
 381   auto *To = reinterpret_cast<u32 *>(Buf);
 382
 383   // The first entry is not a section number but a flag.
 384   *To++ = From[0];
 385
 386   // Adjust section numbers because section numbers in an input object
 387   // files are different in the output.
 388   ArrayRef<InputSectionBase *> Sections = File->getSections();
 389   for (uint32_t Idx : From.slice(1))
 390     *To++ = Sections[Idx]->getOutputSection()->SectionIndex;
 391 }
 392
 393 InputSectionBase *InputSection::getRelocatedSection() const {
 394   if (!File || (Type != SHT_RELA && Type != SHT_REL))
 395     return nullptr;
 396   ArrayRef<InputSectionBase *> Sections = File->getSections();
 397   return Sections[Info];
 398 }
 399
 400 // This is used for -r and --emit-relocs. We can't use memcpy to copy
 401 // relocations because we need to update symbol table offset and section index
 402 // for each relocation. So we copy relocations one by one.
 403 template <class ELFT, class RelTy>
 404 void InputSection::copyRelocations(uint8_t *Buf, ArrayRef<RelTy> Rels) {
 405   InputSectionBase *Sec = getRelocatedSection();
 406
 407   for (const RelTy &Rel : Rels) {
 408     RelType Type = Rel.getType(Config->IsMips64EL);
 409     Symbol &Sym = getFile<ELFT>()->getRelocTargetSym(Rel);
 410
 411     auto *P = reinterpret_cast<typename ELFT::Rela *>(Buf);
 412     Buf += sizeof(RelTy);
 413
 414     if (RelTy::IsRela)
 415       P->r_addend = getAddend<ELFT>(Rel);
 416
 417     // Output section VA is zero for -r, so r_offset is an offset within the
 418     // section, but for --emit-relocs it is an virtual address.
 419     P->r_offset = Sec->getVA(Rel.r_offset);
 420     P->setSymbolAndType(In.SymTab->getSymbolIndex(&Sym), Type,
 421                         Config->IsMips64EL);
 422
 423     if (Sym.Type == STT_SECTION) {
 424       // We combine multiple section symbols into only one per
 425       // section. This means we have to update the addend. That is
 426       // trivial for Elf_Rela, but for Elf_Rel we have to write to the
 427       // section data. We do that by adding to the Relocation vector.
 428
 429       // .eh_frame is horribly special and can reference discarded sections. To
 430       // avoid having to parse and recreate .eh_frame, we just replace any
 431       // relocation in it pointing to discarded sections with R_*_NONE, which
 432       // hopefully creates a frame that is ignored at runtime.
 433       auto *D = dyn_cast<Defined>(&Sym);
 434       if (!D) {
 435         error("STT_SECTION symbol should be defined");
 436         continue;
 437       }
 438       SectionBase *Section = D->Section->Repl;
 439       if (!Section->Live) {
 440         P->setSymbolAndType(0, 0, false);
 441         continue;
 442       }
 443
 444       int64_t Addend = getAddend<ELFT>(Rel);
 445       const uint8_t *BufLoc = Sec->data().begin() + Rel.r_offset;
 446       if (!RelTy::IsRela)
 447         Addend = Target->getImplicitAddend(BufLoc, Type);
 448
 449       if (Config->EMachine == EM_MIPS && Config->Relocatable &&
 450           Target->getRelExpr(Type, Sym, BufLoc) == R_MIPS_GOTREL) {
 451         // Some MIPS relocations depend on "gp" value. By default,
 452         // this value has 0x7ff0 offset from a .got section. But
 453         // relocatable files produced by a complier or a linker
 454         // might redefine this default value and we must use it
 455         // for a calculation of the relocation result. When we
 456         // generate EXE or DSO it's trivial. Generating a relocatable
 457         // output is more difficult case because the linker does
 458         // not calculate relocations in this mode and loses
 459         // individual "gp" values used by each input object file.
 460         // As a workaround we add the "gp" value to the relocation
 461         // addend and save it back to the file.
 462         Addend += Sec->getFile<ELFT>()->MipsGp0;
 463       }
 464
 465       if (RelTy::IsRela)
 466         P->r_addend = Sym.getVA(Addend) - Section->getOutputSection()->Addr;
 467       else if (Config->Relocatable)
 468         Sec->Relocations.push_back({R_ABS, Type, Rel.r_offset, Addend, &Sym});
 469     }
 470   }
 471 }
 472
 473 // The ARM and AArch64 ABI handle pc-relative relocations to undefined weak
 474 // references specially. The general rule is that the value of the symbol in
 475 // this context is the address of the place P. A further special case is that
 476 // branch relocations to an undefined weak reference resolve to the next
 477 // instruction.
 478 static uint32_t getARMUndefinedRelativeWeakVA(RelType Type, uint32_t A,
 479                                               uint32_t P) {
 480   switch (Type) {
 481   // Unresolved branch relocations to weak references resolve to next
 482   // instruction, this will be either 2 or 4 bytes on from P.
 483   case R_ARM_THM_JUMP11:
 484     return P + 2 + A;
 485   case R_ARM_CALL:
 486   case R_ARM_JUMP24:
 487   case R_ARM_PC24:
 488   case R_ARM_PLT32:
 489   case R_ARM_PREL31:
 490   case R_ARM_THM_JUMP19:
 491   case R_ARM_THM_JUMP24:
 492     return P + 4 + A;
 493   case R_ARM_THM_CALL:
 494     // We don't want an interworking BLX to ARM
 495     return P + 5 + A;
 496   // Unresolved non branch pc-relative relocations
 497   // R_ARM_TARGET2 which can be resolved relatively is not present as it never
 498   // targets a weak-reference.
 499   case R_ARM_MOVW_PREL_NC:
 500   case R_ARM_MOVT_PREL:
 501   case R_ARM_REL32:
 502   case R_ARM_THM_MOVW_PREL_NC:
 503   case R_ARM_THM_MOVT_PREL:
 504     return P + A;
 505   }
 506   llvm_unreachable("ARM pc-relative relocation expected\n");
 507 }
 508
 509 // The comment above getARMUndefinedRelativeWeakVA applies to this function.
 510 static uint64_t getAArch64UndefinedRelativeWeakVA(uint64_t Type, uint64_t A,
 511                                                   uint64_t P) {
 512   switch (Type) {
 513   // Unresolved branch relocations to weak references resolve to next
 514   // instruction, this is 4 bytes on from P.
 515   case R_AARCH64_CALL26:
 516   case R_AARCH64_CONDBR19:
 517   case R_AARCH64_JUMP26:
 518   case R_AARCH64_TSTBR14:
 519     return P + 4 + A;
 520   // Unresolved non branch pc-relative relocations
 521   case R_AARCH64_PREL16:
 522   case R_AARCH64_PREL32:
 523   case R_AARCH64_PREL64:
 524   case R_AARCH64_ADR_PREL_LO21:
 525   case R_AARCH64_LD_PREL_LO19:
 526     return P + A;
 527   }
 528   llvm_unreachable("AArch64 pc-relative relocation expected\n");
 529 }
 530
 531 // ARM SBREL relocations are of the form S + A - B where B is the static base
 532 // The ARM ABI defines base to be "addressing origin of the output segment
 533 // defining the symbol S". We defined the "addressing origin"/static base to be
 534 // the base of the PT_LOAD segment containing the Sym.
 535 // The procedure call standard only defines a Read Write Position Independent
 536 // RWPI variant so in practice we should expect the static base to be the base
 537 // of the RW segment.
 538 static uint64_t getARMStaticBase(const Symbol &Sym) {
 539   OutputSection *OS = Sym.getOutputSection();
 540   if (!OS || !OS->PtLoad || !OS->PtLoad->FirstSec)
 541     fatal("SBREL relocation to " + Sym.getName() + " without static base");
 542   return OS->PtLoad->FirstSec->Addr;
 543 }
 544
 545 // For R_RISCV_PC_INDIRECT (R_RISCV_PCREL_LO12_{I,S}), the symbol actually
 546 // points the corresponding R_RISCV_PCREL_HI20 relocation, and the target VA
 547 // is calculated using PCREL_HI20's symbol.
 548 //
 549 // This function returns the R_RISCV_PCREL_HI20 relocation from
 550 // R_RISCV_PCREL_LO12's symbol and addend.
 551 static Relocation *getRISCVPCRelHi20(const Symbol *Sym, uint64_t Addend) {
 552   const Defined *D = cast<Defined>(Sym);
 553   InputSection *IS = cast<InputSection>(D->Section);
 554
 555   if (Addend != 0)
 556     warn("Non-zero addend in R_RISCV_PCREL_LO12 relocation to " +
 557          IS->getObjMsg(D->Value) + " is ignored");
 558
 559   // Relocations are sorted by offset, so we can use std::equal_range to do
 560   // binary search.
 561   auto Range = std::equal_range(IS->Relocations.begin(), IS->Relocations.end(),
 562                                 D->Value, RelocationOffsetComparator{});
 563   for (auto It = std::get<0>(Range); It != std::get<1>(Range); ++It)
 564     if (isRelExprOneOf<R_PC>(It->Expr))
 565       return &*It;
 566
 567   error("R_RISCV_PCREL_LO12 relocation points to " + IS->getObjMsg(D->Value) +
 568         " without an associated R_RISCV_PCREL_HI20 relocation");
 569   return nullptr;
 570 }
 571
 572 // A TLS symbol's virtual address is relative to the TLS segment. Add a
 573 // target-specific adjustment to produce a thread-pointer-relative offset.
 574 static int64_t getTlsTpOffset() {
 575   switch (Config->EMachine) {
 576   case EM_ARM:
 577   case EM_AARCH64:
 578     // Variant 1. The thread pointer points to a TCB with a fixed 2-word size,
 579     // followed by a variable amount of alignment padding, followed by the TLS
 580     // segment.
 581     //
 582     // NB: While the ARM/AArch64 ABI formally has a 2-word TCB size, lld
 583     // effectively increases the TCB size to 8 words for Android compatibility.
 584     // It accomplishes this by increasing the segment's alignment.
 585     return alignTo(Config->Wordsize * 2, Out::TlsPhdr->p_align);
 586   case EM_386:
 587   case EM_X86_64:
 588     // Variant 2. The TLS segment is located just before the thread pointer.
 589     return -Out::TlsPhdr->p_memsz;
 590   case EM_PPC64:
 591     // The thread pointer points to a fixed offset from the start of the
 592     // executable's TLS segment. An offset of 0x7000 allows a signed 16-bit
 593     // offset to reach 0x1000 of TCB/thread-library data and 0xf000 of the
 594     // program's TLS segment.
 595     return -0x7000;
 596   default:
 597     llvm_unreachable("unhandled Config->EMachine");
 598   }
 599 }
 600
 601 static uint64_t getRelocTargetVA(const InputFile *File, RelType Type, int64_t A,
 602                                  uint64_t P, const Symbol &Sym, RelExpr Expr) {
 603   switch (Expr) {
 604   case R_INVALID:
 605     return 0;
 606   case R_ABS:
 607   case R_RELAX_TLS_LD_TO_LE_ABS:
 608   case R_RELAX_GOT_PC_NOPIC:
 609     return Sym.getVA(A);
 610   case R_ADDEND:
 611     return A;
 612   case R_ARM_SBREL:
 613     return Sym.getVA(A) - getARMStaticBase(Sym);
 614   case R_GOT:
 615   case R_GOT_PLT:
 616   case R_RELAX_TLS_GD_TO_IE_ABS:
 617     return Sym.getGotVA() + A;
 618   case R_GOTONLY_PC:
 619     return In.Got->getVA() + A - P;
 620   case R_GOTONLY_PC_FROM_END:
 621     return In.Got->getVA() + A - P + In.Got->getSize();
 622   case R_GOTREL:
 623     return Sym.getVA(A) - In.Got->getVA();
 624   case R_GOTREL_FROM_END:
 625     return Sym.getVA(A) - In.Got->getVA() - In.Got->getSize();
 626   case R_GOT_FROM_END:
 627   case R_RELAX_TLS_GD_TO_IE_END:
 628     return Sym.getGotOffset() + A - In.Got->getSize();
 629   case R_TLSLD_GOT_OFF:
 630   case R_GOT_OFF:
 631   case R_RELAX_TLS_GD_TO_IE_GOT_OFF:
 632     return Sym.getGotOffset() + A;
 633   case R_AARCH64_GOT_PAGE_PC:
 634   case R_AARCH64_GOT_PAGE_PC_PLT:
 635   case R_AARCH64_RELAX_TLS_GD_TO_IE_PAGE_PC:
 636     return getAArch64Page(Sym.getGotVA() + A) - getAArch64Page(P);
 637   case R_GOT_PC:
 638   case R_RELAX_TLS_GD_TO_IE:
 639     return Sym.getGotVA() + A - P;
 640   case R_HEXAGON_GOT:
 641     return Sym.getGotVA() - In.GotPlt->getVA();
 642   case R_MIPS_GOTREL:
 643     return Sym.getVA(A) - In.MipsGot->getGp(File);
 644   case R_MIPS_GOT_GP:
 645     return In.MipsGot->getGp(File) + A;
 646   case R_MIPS_GOT_GP_PC: {
 647     // R_MIPS_LO16 expression has R_MIPS_GOT_GP_PC type iif the target
 648     // is _gp_disp symbol. In that case we should use the following
 649     // formula for calculation "AHL + GP - P + 4". For details see p. 4-19 at
 650     // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
 651     // microMIPS variants of these relocations use slightly different
 652     // expressions: AHL + GP - P + 3 for %lo() and AHL + GP - P - 1 for %hi()
 653     // to correctly handle less-sugnificant bit of the microMIPS symbol.
 654     uint64_t V = In.MipsGot->getGp(File) + A - P;
 655     if (Type == R_MIPS_LO16 || Type == R_MICROMIPS_LO16)
 656       V += 4;
 657     if (Type == R_MICROMIPS_LO16 || Type == R_MICROMIPS_HI16)
 658       V -= 1;
 659     return V;
 660   }
 661   case R_MIPS_GOT_LOCAL_PAGE:
 662     // If relocation against MIPS local symbol requires GOT entry, this entry
 663     // should be initialized by 'page address'. This address is high 16-bits
 664     // of sum the symbol's value and the addend.
 665     return In.MipsGot->getVA() + In.MipsGot->getPageEntryOffset(File, Sym, A) -
 666            In.MipsGot->getGp(File);
 667   case R_MIPS_GOT_OFF:
 668   case R_MIPS_GOT_OFF32:
 669     // In case of MIPS if a GOT relocation has non-zero addend this addend
 670     // should be applied to the GOT entry content not to the GOT entry offset.
 671     // That is why we use separate expression type.
 672     return In.MipsGot->getVA() + In.MipsGot->getSymEntryOffset(File, Sym, A) -
 673            In.MipsGot->getGp(File);
 674   case R_MIPS_TLSGD:
 675     return In.MipsGot->getVA() + In.MipsGot->getGlobalDynOffset(File, Sym) -
 676            In.MipsGot->getGp(File);
 677   case R_MIPS_TLSLD:
 678     return In.MipsGot->getVA() + In.MipsGot->getTlsIndexOffset(File) -
 679            In.MipsGot->getGp(File);
 680   case R_AARCH64_PAGE_PC: {
 681     uint64_t Val = Sym.isUndefWeak() ? P + A : Sym.getVA(A);
 682     return getAArch64Page(Val) - getAArch64Page(P);
 683   }
 684   case R_AARCH64_PLT_PAGE_PC: {
 685     uint64_t Val = Sym.isUndefWeak() ? P + A : Sym.getPltVA() + A;
 686     return getAArch64Page(Val) - getAArch64Page(P);
 687   }
 688   case R_RISCV_PC_INDIRECT: {
 689     if (const Relocation *HiRel = getRISCVPCRelHi20(&Sym, A))
 690       return getRelocTargetVA(File, HiRel->Type, HiRel->Addend, Sym.getVA(),
 691                               *HiRel->Sym, HiRel->Expr);
 692     return 0;
 693   }
 694   case R_PC: {
 695     uint64_t Dest;
 696     if (Sym.isUndefWeak()) {
 697       // On ARM and AArch64 a branch to an undefined weak resolves to the
 698       // next instruction, otherwise the place.
 699       if (Config->EMachine == EM_ARM)
 700         Dest = getARMUndefinedRelativeWeakVA(Type, A, P);
 701       else if (Config->EMachine == EM_AARCH64)
 702         Dest = getAArch64UndefinedRelativeWeakVA(Type, A, P);
 703       else
 704         Dest = Sym.getVA(A);
 705     } else {
 706       Dest = Sym.getVA(A);
 707     }
 708     return Dest - P;
 709   }
 710   case R_PLT:
 711     return Sym.getPltVA() + A;
 712   case R_PLT_PC:
 713   case R_PPC_CALL_PLT:
 714     return Sym.getPltVA() + A - P;
 715   case R_PPC_CALL: {
 716     uint64_t SymVA = Sym.getVA(A);
 717     // If we have an undefined weak symbol, we might get here with a symbol
 718     // address of zero. That could overflow, but the code must be unreachable,
 719     // so don't bother doing anything at all.
 720     if (!SymVA)
 721       return 0;
 722
 723     // PPC64 V2 ABI describes two entry points to a function. The global entry
 724     // point is used for calls where the caller and callee (may) have different
 725     // TOC base pointers and r2 needs to be modified to hold the TOC base for
 726     // the callee. For local calls the caller and callee share the same
 727     // TOC base and so the TOC pointer initialization code should be skipped by
 728     // branching to the local entry point.
 729     return SymVA - P + getPPC64GlobalEntryToLocalEntryOffset(Sym.StOther);
 730   }
 731   case R_PPC_TOC:
 732     return getPPC64TocBase() + A;
 733   case R_RELAX_GOT_PC:
 734     return Sym.getVA(A) - P;
 735   case R_RELAX_TLS_GD_TO_LE:
 736   case R_RELAX_TLS_IE_TO_LE:
 737   case R_RELAX_TLS_LD_TO_LE:
 738   case R_TLS:
 739     // A weak undefined TLS symbol resolves to the base of the TLS
 740     // block, i.e. gets a value of zero. If we pass --gc-sections to
 741     // lld and .tbss is not referenced, it gets reclaimed and we don't
 742     // create a TLS program header. Therefore, we resolve this
 743     // statically to zero.
 744     if (Sym.isTls() && Sym.isUndefWeak())
 745       return 0;
 746     return Sym.getVA(A) + getTlsTpOffset();
 747   case R_RELAX_TLS_GD_TO_LE_NEG:
 748   case R_NEG_TLS:
 749     return Out::TlsPhdr->p_memsz - Sym.getVA(A);
 750   case R_SIZE:
 751     return Sym.getSize() + A;
 752   case R_TLSDESC:
 753     return In.Got->getGlobalDynAddr(Sym) + A;
 754   case R_AARCH64_TLSDESC_PAGE:
 755     return getAArch64Page(In.Got->getGlobalDynAddr(Sym) + A) -
 756            getAArch64Page(P);
 757   case R_TLSGD_GOT:
 758     return In.Got->getGlobalDynOffset(Sym) + A;
 759   case R_TLSGD_GOT_FROM_END:
 760     return In.Got->getGlobalDynOffset(Sym) + A - In.Got->getSize();
 761   case R_TLSGD_PC:
 762     return In.Got->getGlobalDynAddr(Sym) + A - P;
 763   case R_TLSLD_GOT_FROM_END:
 764     return In.Got->getTlsIndexOff() + A - In.Got->getSize();
 765   case R_TLSLD_GOT:
 766     return In.Got->getTlsIndexOff() + A;
 767   case R_TLSLD_PC:
 768     return In.Got->getTlsIndexVA() + A - P;
 769   default:
 770     llvm_unreachable("invalid expression");
 771   }
 772 }
 773
 774 // This function applies relocations to sections without SHF_ALLOC bit.
 775 // Such sections are never mapped to memory at runtime. Debug sections are
 776 // an example. Relocations in non-alloc sections are much easier to
 777 // handle than in allocated sections because it will never need complex
 778 // treatement such as GOT or PLT (because at runtime no one refers them).
 779 // So, we handle relocations for non-alloc sections directly in this
 780 // function as a performance optimization.
 781 template <class ELFT, class RelTy>
 782 void InputSection::relocateNonAlloc(uint8_t *Buf, ArrayRef<RelTy> Rels) {
 783   const unsigned Bits = sizeof(typename ELFT::uint) * 8;
 784
 785   for (const RelTy &Rel : Rels) {
 786     RelType Type = Rel.getType(Config->IsMips64EL);
 787
 788     // GCC 8.0 or earlier have a bug that they emit R_386_GOTPC relocations
 789     // against _GLOBAL_OFFSET_TABLE_ for .debug_info. The bug has been fixed
 790     // in 2017 (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82630), but we
 791     // need to keep this bug-compatible code for a while.
 792     if (Config->EMachine == EM_386 && Type == R_386_GOTPC)
 793       continue;
 794
 795     uint64_t Offset = getOffset(Rel.r_offset);
 796     uint8_t *BufLoc = Buf + Offset;
 797     int64_t Addend = getAddend<ELFT>(Rel);
 798     if (!RelTy::IsRela)
 799       Addend += Target->getImplicitAddend(BufLoc, Type);
 800
 801     Symbol &Sym = getFile<ELFT>()->getRelocTargetSym(Rel);
 802     RelExpr Expr = Target->getRelExpr(Type, Sym, BufLoc);
 803     if (Expr == R_NONE)
 804       continue;
 805
 806     if (Expr != R_ABS) {
 807       std::string Msg = getLocation<ELFT>(Offset) +
 808                         ": has non-ABS relocation " + toString(Type) +
 809                         " against symbol '" + toString(Sym) + "'";
 810       if (Expr != R_PC) {
 811         error(Msg);
 812         return;
 813       }
 814
 815       // If the control reaches here, we found a PC-relative relocation in a
 816       // non-ALLOC section. Since non-ALLOC section is not loaded into memory
 817       // at runtime, the notion of PC-relative doesn't make sense here. So,
 818       // this is a usage error. However, GNU linkers historically accept such
 819       // relocations without any errors and relocate them as if they were at
 820       // address 0. For bug-compatibilty, we accept them with warnings. We
 821       // know Steel Bank Common Lisp as of 2018 have this bug.
 822       warn(Msg);
 823       Target->relocateOne(BufLoc, Type,
 824                           SignExtend64<Bits>(Sym.getVA(Addend - Offset)));
 825       continue;
 826     }
 827
 828     if (Sym.isTls() && !Out::TlsPhdr)
 829       Target->relocateOne(BufLoc, Type, 0);
 830     else
 831       Target->relocateOne(BufLoc, Type, SignExtend64<Bits>(Sym.getVA(Addend)));
 832   }
 833 }
 834
 835 // This is used when '-r' is given.
 836 // For REL targets, InputSection::copyRelocations() may store artificial
 837 // relocations aimed to update addends. They are handled in relocateAlloc()
 838 // for allocatable sections, and this function does the same for
 839 // non-allocatable sections, such as sections with debug information.
 840 static void relocateNonAllocForRelocatable(InputSection *Sec, uint8_t *Buf) {
 841   const unsigned Bits = Config->Is64 ? 64 : 32;
 842
 843   for (const Relocation &Rel : Sec->Relocations) {
 844     // InputSection::copyRelocations() adds only R_ABS relocations.
 845     assert(Rel.Expr == R_ABS);
 846     uint8_t *BufLoc = Buf + Rel.Offset + Sec->OutSecOff;
 847     uint64_t TargetVA = SignExtend64(Rel.Sym->getVA(Rel.Addend), Bits);
 848     Target->relocateOne(BufLoc, Rel.Type, TargetVA);
 849   }
 850 }
 851
 852 template <class ELFT>
 853 void InputSectionBase::relocate(uint8_t *Buf, uint8_t *BufEnd) {
 854   if (Flags & SHF_EXECINSTR)
 855     adjustSplitStackFunctionPrologues<ELFT>(Buf, BufEnd);
 856
 857   if (Flags & SHF_ALLOC) {
 858     relocateAlloc(Buf, BufEnd);
 859     return;
 860   }
 861
 862   auto *Sec = cast<InputSection>(this);
 863   if (Config->Relocatable)
 864     relocateNonAllocForRelocatable(Sec, Buf);
 865   else if (Sec->AreRelocsRela)
 866     Sec->relocateNonAlloc<ELFT>(Buf, Sec->template relas<ELFT>());
 867   else
 868     Sec->relocateNonAlloc<ELFT>(Buf, Sec->template rels<ELFT>());
 869 }
 870
 871 void InputSectionBase::relocateAlloc(uint8_t *Buf, uint8_t *BufEnd) {
 872   assert(Flags & SHF_ALLOC);
 873   const unsigned Bits = Config->Wordsize * 8;
 874
 875   for (const Relocation &Rel : Relocations) {
 876     uint64_t Offset = Rel.Offset;
 877     if (auto *Sec = dyn_cast<InputSection>(this))
 878       Offset += Sec->OutSecOff;
 879     uint8_t *BufLoc = Buf + Offset;
 880     RelType Type = Rel.Type;
 881
 882     uint64_t AddrLoc = getOutputSection()->Addr + Offset;
 883     RelExpr Expr = Rel.Expr;
 884     uint64_t TargetVA = SignExtend64(
 885         getRelocTargetVA(File, Type, Rel.Addend, AddrLoc, *Rel.Sym, Expr),
 886         Bits);
 887
 888     switch (Expr) {
 889     case R_RELAX_GOT_PC:
 890     case R_RELAX_GOT_PC_NOPIC:
 891       Target->relaxGot(BufLoc, TargetVA);
 892       break;
 893     case R_RELAX_TLS_IE_TO_LE:
 894       Target->relaxTlsIeToLe(BufLoc, Type, TargetVA);
 895       break;
 896     case R_RELAX_TLS_LD_TO_LE:
 897     case R_RELAX_TLS_LD_TO_LE_ABS:
 898       Target->relaxTlsLdToLe(BufLoc, Type, TargetVA);
 899       break;
 900     case R_RELAX_TLS_GD_TO_LE:
 901     case R_RELAX_TLS_GD_TO_LE_NEG:
 902       Target->relaxTlsGdToLe(BufLoc, Type, TargetVA);
 903       break;
 904     case R_AARCH64_RELAX_TLS_GD_TO_IE_PAGE_PC:
 905     case R_RELAX_TLS_GD_TO_IE:
 906     case R_RELAX_TLS_GD_TO_IE_ABS:
 907     case R_RELAX_TLS_GD_TO_IE_GOT_OFF:
 908     case R_RELAX_TLS_GD_TO_IE_END:
 909       Target->relaxTlsGdToIe(BufLoc, Type, TargetVA);
 910       break;
 911     case R_PPC_CALL:
 912       // If this is a call to __tls_get_addr, it may be part of a TLS
 913       // sequence that has been relaxed and turned into a nop. In this
 914       // case, we don't want to handle it as a call.
 915       if (read32(BufLoc) == 0x60000000) // nop
 916         break;
 917
 918       // Patch a nop (0x60000000) to a ld.
 919       if (Rel.Sym->NeedsTocRestore) {
 920         if (BufLoc + 8 > BufEnd || read32(BufLoc + 4) != 0x60000000) {
 921           error(getErrorLocation(BufLoc) + "call lacks nop, can't restore toc");
 922           break;
 923         }
 924         write32(BufLoc + 4, 0xe8410018); // ld %r2, 24(%r1)
 925       }
 926       Target->relocateOne(BufLoc, Type, TargetVA);
 927       break;
 928     default:
 929       Target->relocateOne(BufLoc, Type, TargetVA);
 930       break;
 931     }
 932   }
 933 }
 934
 935 // For each function-defining prologue, find any calls to __morestack,
 936 // and replace them with calls to __morestack_non_split.
 937 static void switchMorestackCallsToMorestackNonSplit(
 938     DenseSet<Defined *> &Prologues, std::vector<Relocation *> &MorestackCalls) {
 939
 940   // If the target adjusted a function's prologue, all calls to
 941   // __morestack inside that function should be switched to
 942   // __morestack_non_split.
 943   Symbol *MoreStackNonSplit = Symtab->find("__morestack_non_split");
 944   if (!MoreStackNonSplit) {
 945     error("Mixing split-stack objects requires a definition of "
 946           "__morestack_non_split");
 947     return;
 948   }
 949
 950   // Sort both collections to compare addresses efficiently.
 951   llvm::sort(MorestackCalls, [](const Relocation *L, const Relocation *R) {
 952     return L->Offset < R->Offset;
 953   });
 954   std::vector<Defined *> Functions(Prologues.begin(), Prologues.end());
 955   llvm::sort(Functions, [](const Defined *L, const Defined *R) {
 956     return L->Value < R->Value;
 957   });
 958
 959   auto It = MorestackCalls.begin();
 960   for (Defined *F : Functions) {
 961     // Find the first call to __morestack within the function.
 962     while (It != MorestackCalls.end() && (*It)->Offset < F->Value)
 963       ++It;
 964     // Adjust all calls inside the function.
 965     while (It != MorestackCalls.end() && (*It)->Offset < F->Value + F->Size) {
 966       (*It)->Sym = MoreStackNonSplit;
 967       ++It;
 968     }
 969   }
 970 }
 971
 972 static bool enclosingPrologueAttempted(uint64_t Offset,
 973                                        const DenseSet<Defined *> &Prologues) {
 974   for (Defined *F : Prologues)
 975     if (F->Value <= Offset && Offset < F->Value + F->Size)
 976       return true;
 977   return false;
 978 }
 979
 980 // If a function compiled for split stack calls a function not
 981 // compiled for split stack, then the caller needs its prologue
 982 // adjusted to ensure that the called function will have enough stack
 983 // available. Find those functions, and adjust their prologues.
 984 template <class ELFT>
 985 void InputSectionBase::adjustSplitStackFunctionPrologues(uint8_t *Buf,
 986                                                          uint8_t *End) {
 987   if (!getFile<ELFT>()->SplitStack)
 988     return;
 989   DenseSet<Defined *> Prologues;
 990   std::vector<Relocation *> MorestackCalls;
 991
 992   for (Relocation &Rel : Relocations) {
 993     // Local symbols can't possibly be cross-calls, and should have been
 994     // resolved long before this line.
 995     if (Rel.Sym->isLocal())
 996       continue;
 997
 998     // Ignore calls into the split-stack api.
 999     if (Rel.Sym->getName().startswith("__morestack")) {
1000       if (Rel.Sym->getName().equals("__morestack"))
1001         MorestackCalls.push_back(&Rel);
1002       continue;
1003     }
1004
1005     // A relocation to non-function isn't relevant. Sometimes
1006     // __morestack is not marked as a function, so this check comes
1007     // after the name check.
1008     if (Rel.Sym->Type != STT_FUNC)
1009       continue;
1010
1011     // If the callee's-file was compiled with split stack, nothing to do.  In
1012     // this context, a "Defined" symbol is one "defined by the binary currently
1013     // being produced". So an "undefined" symbol might be provided by a shared
1014     // library. It is not possible to tell how such symbols were compiled, so be
1015     // conservative.
1016     if (Defined *D = dyn_cast<Defined>(Rel.Sym))
1017       if (InputSection *IS = cast_or_null<InputSection>(D->Section))
1018         if (!IS || !IS->getFile<ELFT>() || IS->getFile<ELFT>()->SplitStack)
1019           continue;
1020
1021     if (enclosingPrologueAttempted(Rel.Offset, Prologues))
1022       continue;
1023
1024     if (Defined *F = getEnclosingFunction<ELFT>(Rel.Offset)) {
1025       Prologues.insert(F);
1026       if (Target->adjustPrologueForCrossSplitStack(Buf + getOffset(F->Value),
1027                                                    End, F->StOther))
1028         continue;
1029       if (!getFile<ELFT>()->SomeNoSplitStack)
1030         error(lld::toString(this) + ": " + F->getName() +
1031               " (with -fsplit-stack) calls " + Rel.Sym->getName() +
1032               " (without -fsplit-stack), but couldn't adjust its prologue");
1033     }
1034   }
1035
1036   if (Target->NeedsMoreStackNonSplit)
1037     switchMorestackCallsToMorestackNonSplit(Prologues, MorestackCalls);
1038 }
1039
1040 template <class ELFT> void InputSection::writeTo(uint8_t *Buf) {
1041   if (Type == SHT_NOBITS)
1042     return;
1043
1044   if (auto *S = dyn_cast<SyntheticSection>(this)) {
1045     S->writeTo(Buf + OutSecOff);
1046     return;
1047   }
1048
1049   // If -r or --emit-relocs is given, then an InputSection
1050   // may be a relocation section.
1051   if (Type == SHT_RELA) {
1052     copyRelocations<ELFT>(Buf + OutSecOff, getDataAs<typename ELFT::Rela>());
1053     return;
1054   }
1055   if (Type == SHT_REL) {
1056     copyRelocations<ELFT>(Buf + OutSecOff, getDataAs<typename ELFT::Rel>());
1057     return;
1058   }
1059
1060   // If -r is given, we may have a SHT_GROUP section.
1061   if (Type == SHT_GROUP) {
1062     copyShtGroup<ELFT>(Buf + OutSecOff);
1063     return;
1064   }
1065
1066   // If this is a compressed section, uncompress section contents directly
1067   // to the buffer.
1068   if (UncompressedSize >= 0 && !UncompressedBuf) {
1069     size_t Size = UncompressedSize;
1070     if (Error E = zlib::uncompress(toStringRef(RawData),
1071                                    (char *)(Buf + OutSecOff), Size))
1072       fatal(toString(this) +
1073             ": uncompress failed: " + llvm::toString(std::move(E)));
1074     uint8_t *BufEnd = Buf + OutSecOff + Size;
1075     relocate<ELFT>(Buf, BufEnd);
1076     return;
1077   }
1078
1079   // Copy section contents from source object file to output file
1080   // and then apply relocations.
1081   memcpy(Buf + OutSecOff, data().data(), data().size());
1082   uint8_t *BufEnd = Buf + OutSecOff + data().size();
1083   relocate<ELFT>(Buf, BufEnd);
1084 }
1085
1086 void InputSection::replace(InputSection *Other) {
1087   Alignment = std::max(Alignment, Other->Alignment);
1088   Other->Repl = Repl;
1089   Other->Live = false;
1090 }
1091
1092 template <class ELFT>
1093 EhInputSection::EhInputSection(ObjFile<ELFT> &F,
1094                                const typename ELFT::Shdr &Header,
1095                                StringRef Name)
1096     : InputSectionBase(F, Header, Name, InputSectionBase::EHFrame) {}
1097
1098 SyntheticSection *EhInputSection::getParent() const {
1099   return cast_or_null<SyntheticSection>(Parent);
1100 }
1101
1102 // Returns the index of the first relocation that points to a region between
1103 // Begin and Begin+Size.
1104 template <class IntTy, class RelTy>
1105 static unsigned getReloc(IntTy Begin, IntTy Size, const ArrayRef<RelTy> &Rels,
1106                          unsigned &RelocI) {
1107   // Start search from RelocI for fast access. That works because the
1108   // relocations are sorted in .eh_frame.
1109   for (unsigned N = Rels.size(); RelocI < N; ++RelocI) {
1110     const RelTy &Rel = Rels[RelocI];
1111     if (Rel.r_offset < Begin)
1112       continue;
1113
1114     if (Rel.r_offset < Begin + Size)
1115       return RelocI;
1116     return -1;
1117   }
1118   return -1;
1119 }
1120
1121 // .eh_frame is a sequence of CIE or FDE records.
1122 // This function splits an input section into records and returns them.
1123 template <class ELFT> void EhInputSection::split() {
1124   if (AreRelocsRela)
1125     split<ELFT>(relas<ELFT>());
1126   else
1127     split<ELFT>(rels<ELFT>());
1128 }
1129
1130 template <class ELFT, class RelTy>
1131 void EhInputSection::split(ArrayRef<RelTy> Rels) {
1132   unsigned RelI = 0;
1133   for (size_t Off = 0, End = data().size(); Off != End;) {
1134     size_t Size = readEhRecordSize(this, Off);
1135     Pieces.emplace_back(Off, this, Size, getReloc(Off, Size, Rels, RelI));
1136     // The empty record is the end marker.
1137     if (Size == 4)
1138       break;
1139     Off += Size;
1140   }
1141 }
1142
1143 static size_t findNull(StringRef S, size_t EntSize) {
1144   // Optimize the common case.
1145   if (EntSize == 1)
1146     return S.find(0);
1147
1148   for (unsigned I = 0, N = S.size(); I != N; I += EntSize) {
1149     const char *B = S.begin() + I;
1150     if (std::all_of(B, B + EntSize, [](char C) { return C == 0; }))
1151       return I;
1152   }
1153   return StringRef::npos;
1154 }
1155
1156 SyntheticSection *MergeInputSection::getParent() const {
1157   return cast_or_null<SyntheticSection>(Parent);
1158 }
1159
1160 // Split SHF_STRINGS section. Such section is a sequence of
1161 // null-terminated strings.
1162 void MergeInputSection::splitStrings(ArrayRef<uint8_t> Data, size_t EntSize) {
1163   size_t Off = 0;
1164   bool IsAlloc = Flags & SHF_ALLOC;
1165   StringRef S = toStringRef(Data);
1166
1167   while (!S.empty()) {
1168     size_t End = findNull(S, EntSize);
1169     if (End == StringRef::npos)
1170       fatal(toString(this) + ": string is not null terminated");
1171     size_t Size = End + EntSize;
1172
1173     Pieces.emplace_back(Off, xxHash64(S.substr(0, Size)), !IsAlloc);
1174     S = S.substr(Size);
1175     Off += Size;
1176   }
1177 }
1178
1179 // Split non-SHF_STRINGS section. Such section is a sequence of
1180 // fixed size records.
1181 void MergeInputSection::splitNonStrings(ArrayRef<uint8_t> Data,
1182                                         size_t EntSize) {
1183   size_t Size = Data.size();
1184   assert((Size % EntSize) == 0);
1185   bool IsAlloc = Flags & SHF_ALLOC;
1186
1187   for (size_t I = 0; I != Size; I += EntSize)
1188     Pieces.emplace_back(I, xxHash64(Data.slice(I, EntSize)), !IsAlloc);
1189 }
1190
1191 template <class ELFT>
1192 MergeInputSection::MergeInputSection(ObjFile<ELFT> &F,
1193                                      const typename ELFT::Shdr &Header,
1194                                      StringRef Name)
1195     : InputSectionBase(F, Header, Name, InputSectionBase::Merge) {}
1196
1197 MergeInputSection::MergeInputSection(uint64_t Flags, uint32_t Type,
1198                                      uint64_t Entsize, ArrayRef<uint8_t> Data,
1199                                      StringRef Name)
1200     : InputSectionBase(nullptr, Flags, Type, Entsize, /*Link*/ 0, /*Info*/ 0,
1201                        /*Alignment*/ Entsize, Data, Name, SectionBase::Merge) {}
1202
1203 // This function is called after we obtain a complete list of input sections
1204 // that need to be linked. This is responsible to split section contents
1205 // into small chunks for further processing.
1206 //
1207 // Note that this function is called from parallelForEach. This must be
1208 // thread-safe (i.e. no memory allocation from the pools).
1209 void MergeInputSection::splitIntoPieces() {
1210   assert(Pieces.empty());
1211
1212   if (Flags & SHF_STRINGS)
1213     splitStrings(data(), Entsize);
1214   else
1215     splitNonStrings(data(), Entsize);
1216 }
1217
1218 SectionPiece *MergeInputSection::getSectionPiece(uint64_t Offset) {
1219   if (this->data().size() <= Offset)
1220     fatal(toString(this) + ": offset is outside the section");
1221
1222   // If Offset is not at beginning of a section piece, it is not in the map.
1223   // In that case we need to  do a binary search of the original section piece vector.
1224   auto It2 =
1225       llvm::upper_bound(Pieces, Offset, [](uint64_t Offset, SectionPiece P) {
1226         return Offset < P.InputOff;
1227       });
1228   return &It2[-1];
1229 }
1230
1231 // Returns the offset in an output section for a given input offset.
1232 // Because contents of a mergeable section is not contiguous in output,
1233 // it is not just an addition to a base output offset.
1234 uint64_t MergeInputSection::getParentOffset(uint64_t Offset) const {
1235   // If Offset is not at beginning of a section piece, it is not in the map.
1236   // In that case we need to search from the original section piece vector.
1237   const SectionPiece &Piece =
1238       *(const_cast<MergeInputSection *>(this)->getSectionPiece (Offset));
1239   uint64_t Addend = Offset - Piece.InputOff;
1240   return Piece.OutputOff + Addend;
1241 }
1242
1243 template InputSection::InputSection(ObjFile<ELF32LE> &, const ELF32LE::Shdr &,
1244                                     StringRef);
1245 template InputSection::InputSection(ObjFile<ELF32BE> &, const ELF32BE::Shdr &,
1246                                     StringRef);
1247 template InputSection::InputSection(ObjFile<ELF64LE> &, const ELF64LE::Shdr &,
1248                                     StringRef);
1249 template InputSection::InputSection(ObjFile<ELF64BE> &, const ELF64BE::Shdr &,
1250                                     StringRef);
1251
1252 template std::string InputSectionBase::getLocation<ELF32LE>(uint64_t);
1253 template std::string InputSectionBase::getLocation<ELF32BE>(uint64_t);
1254 template std::string InputSectionBase::getLocation<ELF64LE>(uint64_t);
1255 template std::string InputSectionBase::getLocation<ELF64BE>(uint64_t);
1256
1257 template void InputSection::writeTo<ELF32LE>(uint8_t *);
1258 template void InputSection::writeTo<ELF32BE>(uint8_t *);
1259 template void InputSection::writeTo<ELF64LE>(uint8_t *);
1260 template void InputSection::writeTo<ELF64BE>(uint8_t *);
1261
1262 template MergeInputSection::MergeInputSection(ObjFile<ELF32LE> &,
1263                                               const ELF32LE::Shdr &, StringRef);
1264 template MergeInputSection::MergeInputSection(ObjFile<ELF32BE> &,
1265                                               const ELF32BE::Shdr &, StringRef);
1266 template MergeInputSection::MergeInputSection(ObjFile<ELF64LE> &,
1267                                               const ELF64LE::Shdr &, StringRef);
1268 template MergeInputSection::MergeInputSection(ObjFile<ELF64BE> &,
1269                                               const ELF64BE::Shdr &, StringRef);
1270
1271 template EhInputSection::EhInputSection(ObjFile<ELF32LE> &,
1272                                         const ELF32LE::Shdr &, StringRef);
1273 template EhInputSection::EhInputSection(ObjFile<ELF32BE> &,
1274                                         const ELF32BE::Shdr &, StringRef);
1275 template EhInputSection::EhInputSection(ObjFile<ELF64LE> &,
1276                                         const ELF64LE::Shdr &, StringRef);
1277 template EhInputSection::EhInputSection(ObjFile<ELF64BE> &,
1278                                         const ELF64BE::Shdr &, StringRef);
1279
1280 template void EhInputSection::split<ELF32LE>();
1281 template void EhInputSection::split<ELF32BE>();
1282 template void EhInputSection::split<ELF64LE>();
1283 template void EhInputSection::split<ELF64BE>();