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