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

   1 //===- InputSection.cpp ---------------------------------------------------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "InputSection.h"
  11 #include "Config.h"
  12 #include "EhFrame.h"
  13 #include "Error.h"
  14 #include "InputFiles.h"
  15 #include "LinkerScript.h"
  16 #include "OutputSections.h"
  17 #include "Target.h"
  18 #include "Thunks.h"
  19
  20 #include "llvm/Support/Compression.h"
  21 #include "llvm/Support/Endian.h"
  22
  23 using namespace llvm;
  24 using namespace llvm::ELF;
  25 using namespace llvm::object;
  26 using namespace llvm::support::endian;
  27
  28 using namespace lld;
  29 using namespace lld::elf;
  30
  31 template <class ELFT> bool elf::isDiscarded(InputSectionBase<ELFT> *S) {
  32   return !S || S == &InputSection<ELFT>::Discarded || !S->Live ||
  33          Script<ELFT>::X->isDiscarded(S);
  34 }
  35
  36 template <class ELFT>
  37 InputSectionBase<ELFT>::InputSectionBase(elf::ObjectFile<ELFT> *File,
  38                                          const Elf_Shdr *Header,
  39                                          Kind SectionKind)
  40     : Header(Header), File(File), SectionKind(SectionKind), Repl(this),
  41       Compressed(Header->sh_flags & SHF_COMPRESSED) {
  42   // The garbage collector sets sections' Live bits.
  43   // If GC is disabled, all sections are considered live by default.
  44   Live = !Config->GcSections;
  45
  46   // The ELF spec states that a value of 0 means the section has
  47   // no alignment constraits.
  48   Alignment = std::max<uintX_t>(Header->sh_addralign, 1);
  49 }
  50
  51 template <class ELFT> size_t InputSectionBase<ELFT>::getSize() const {
  52   if (auto *D = dyn_cast<InputSection<ELFT>>(this))
  53     if (D->getThunksSize() > 0)
  54       return D->getThunkOff() + D->getThunksSize();
  55   return Header->sh_size;
  56 }
  57
  58 template <class ELFT> StringRef InputSectionBase<ELFT>::getSectionName() const {
  59   return check(File->getObj().getSectionName(this->Header));
  60 }
  61
  62 template <class ELFT>
  63 ArrayRef<uint8_t> InputSectionBase<ELFT>::getSectionData() const {
  64   if (Compressed)
  65     return ArrayRef<uint8_t>((const uint8_t *)Uncompressed.data(),
  66                              Uncompressed.size());
  67   return check(this->File->getObj().getSectionContents(this->Header));
  68 }
  69
  70 template <class ELFT>
  71 typename ELFT::uint InputSectionBase<ELFT>::getOffset(uintX_t Offset) const {
  72   switch (SectionKind) {
  73   case Regular:
  74     return cast<InputSection<ELFT>>(this)->OutSecOff + Offset;
  75   case EHFrame:
  76     return cast<EhInputSection<ELFT>>(this)->getOffset(Offset);
  77   case Merge:
  78     return cast<MergeInputSection<ELFT>>(this)->getOffset(Offset);
  79   case MipsReginfo:
  80   case MipsOptions:
  81     // MIPS .reginfo and .MIPS.options sections are consumed by the linker,
  82     // and the linker produces a single output section. It is possible that
  83     // input files contain section symbol points to the corresponding input
  84     // section. Redirect it to the produced output section.
  85     if (Offset != 0)
  86       fatal("Unsupported reference to the middle of '" + getSectionName() +
  87             "' section");
  88     return this->OutSec->getVA();
  89   }
  90   llvm_unreachable("invalid section kind");
  91 }
  92
  93 template <class ELFT> void InputSectionBase<ELFT>::uncompress() {
  94   if (!zlib::isAvailable())
  95     fatal("build lld with zlib to enable compressed sections support");
  96
  97   // A compressed section consists of a header of Elf_Chdr type
  98   // followed by compressed data.
  99   ArrayRef<uint8_t> Data =
 100       check(this->File->getObj().getSectionContents(this->Header));
 101   if (Data.size() < sizeof(Elf_Chdr))
 102     fatal("corrupt compressed section");
 103
 104   auto *Hdr = reinterpret_cast<const Elf_Chdr *>(Data.data());
 105   Data = Data.slice(sizeof(Elf_Chdr));
 106
 107   if (Hdr->ch_type != ELFCOMPRESS_ZLIB)
 108     fatal("unsupported compression type");
 109
 110   StringRef Buf((const char *)Data.data(), Data.size());
 111   if (zlib::uncompress(Buf, Uncompressed, Hdr->ch_size) != zlib::StatusOK)
 112     fatal("error uncompressing section");
 113 }
 114
 115 template <class ELFT>
 116 typename ELFT::uint
 117 InputSectionBase<ELFT>::getOffset(const DefinedRegular<ELFT> &Sym) const {
 118   return getOffset(Sym.Value);
 119 }
 120
 121 template <class ELFT>
 122 InputSection<ELFT>::InputSection(elf::ObjectFile<ELFT> *F,
 123                                  const Elf_Shdr *Header)
 124     : InputSectionBase<ELFT>(F, Header, Base::Regular) {}
 125
 126 template <class ELFT>
 127 bool InputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
 128   return S->SectionKind == Base::Regular;
 129 }
 130
 131 template <class ELFT>
 132 InputSectionBase<ELFT> *InputSection<ELFT>::getRelocatedSection() {
 133   assert(this->Header->sh_type == SHT_RELA || this->Header->sh_type == SHT_REL);
 134   ArrayRef<InputSectionBase<ELFT> *> Sections = this->File->getSections();
 135   return Sections[this->Header->sh_info];
 136 }
 137
 138 template <class ELFT>
 139 void InputSection<ELFT>::addThunk(const Thunk<ELFT> *T) {
 140   Thunks.push_back(T);
 141 }
 142
 143 template <class ELFT> uint64_t InputSection<ELFT>::getThunkOff() const {
 144   return this->Header->sh_size;
 145 }
 146
 147 template <class ELFT> uint64_t InputSection<ELFT>::getThunksSize() const {
 148   uint64_t Total = 0;
 149   for (const Thunk<ELFT> *T : Thunks)
 150     Total += T->size();
 151   return Total;
 152 }
 153
 154 // This is used for -r. We can't use memcpy to copy relocations because we need
 155 // to update symbol table offset and section index for each relocation. So we
 156 // copy relocations one by one.
 157 template <class ELFT>
 158 template <class RelTy>
 159 void InputSection<ELFT>::copyRelocations(uint8_t *Buf, ArrayRef<RelTy> Rels) {
 160   InputSectionBase<ELFT> *RelocatedSection = getRelocatedSection();
 161
 162   for (const RelTy &Rel : Rels) {
 163     uint32_t Type = Rel.getType(Config->Mips64EL);
 164     SymbolBody &Body = this->File->getRelocTargetSym(Rel);
 165
 166     RelTy *P = reinterpret_cast<RelTy *>(Buf);
 167     Buf += sizeof(RelTy);
 168
 169     P->r_offset = RelocatedSection->getOffset(Rel.r_offset);
 170     P->setSymbolAndType(Body.DynsymIndex, Type, Config->Mips64EL);
 171   }
 172 }
 173
 174 // Page(Expr) is the page address of the expression Expr, defined
 175 // as (Expr & ~0xFFF). (This applies even if the machine page size
 176 // supported by the platform has a different value.)
 177 static uint64_t getAArch64Page(uint64_t Expr) {
 178   return Expr & (~static_cast<uint64_t>(0xFFF));
 179 }
 180
 181 template <class ELFT>
 182 static typename ELFT::uint getSymVA(uint32_t Type, typename ELFT::uint A,
 183                                     typename ELFT::uint P,
 184                                     const SymbolBody &Body, RelExpr Expr) {
 185   typedef typename ELFT::uint uintX_t;
 186
 187   switch (Expr) {
 188   case R_HINT:
 189     llvm_unreachable("cannot relocate hint relocs");
 190   case R_TLSLD:
 191     return Out<ELFT>::Got->getTlsIndexOff() + A -
 192            Out<ELFT>::Got->getNumEntries() * sizeof(uintX_t);
 193   case R_TLSLD_PC:
 194     return Out<ELFT>::Got->getTlsIndexVA() + A - P;
 195   case R_THUNK_ABS:
 196     return Body.getThunkVA<ELFT>() + A;
 197   case R_THUNK_PC:
 198   case R_THUNK_PLT_PC:
 199     return Body.getThunkVA<ELFT>() + A - P;
 200   case R_PPC_TOC:
 201     return getPPC64TocBase() + A;
 202   case R_TLSGD:
 203     return Out<ELFT>::Got->getGlobalDynOffset(Body) + A -
 204            Out<ELFT>::Got->getNumEntries() * sizeof(uintX_t);
 205   case R_TLSGD_PC:
 206     return Out<ELFT>::Got->getGlobalDynAddr(Body) + A - P;
 207   case R_TLSDESC:
 208     return Out<ELFT>::Got->getGlobalDynAddr(Body) + A;
 209   case R_TLSDESC_PAGE:
 210     return getAArch64Page(Out<ELFT>::Got->getGlobalDynAddr(Body) + A) -
 211            getAArch64Page(P);
 212   case R_PLT:
 213     return Body.getPltVA<ELFT>() + A;
 214   case R_PLT_PC:
 215   case R_PPC_PLT_OPD:
 216     return Body.getPltVA<ELFT>() + A - P;
 217   case R_SIZE:
 218     return Body.getSize<ELFT>() + A;
 219   case R_GOTREL:
 220     return Body.getVA<ELFT>(A) - Out<ELFT>::Got->getVA();
 221   case R_RELAX_TLS_GD_TO_IE_END:
 222   case R_GOT_FROM_END:
 223     return Body.getGotOffset<ELFT>() + A -
 224            Out<ELFT>::Got->getNumEntries() * sizeof(uintX_t);
 225   case R_RELAX_TLS_GD_TO_IE_ABS:
 226   case R_GOT:
 227     return Body.getGotVA<ELFT>() + A;
 228   case R_RELAX_TLS_GD_TO_IE_PAGE_PC:
 229   case R_GOT_PAGE_PC:
 230     return getAArch64Page(Body.getGotVA<ELFT>() + A) - getAArch64Page(P);
 231   case R_RELAX_TLS_GD_TO_IE:
 232   case R_GOT_PC:
 233     return Body.getGotVA<ELFT>() + A - P;
 234   case R_GOTONLY_PC:
 235     return Out<ELFT>::Got->getVA() + A - P;
 236   case R_RELAX_TLS_LD_TO_LE:
 237   case R_RELAX_TLS_IE_TO_LE:
 238   case R_RELAX_TLS_GD_TO_LE:
 239   case R_TLS:
 240     if (Target->TcbSize)
 241       return Body.getVA<ELFT>(A) +
 242              alignTo(Target->TcbSize, Out<ELFT>::TlsPhdr->p_align);
 243     return Body.getVA<ELFT>(A) - Out<ELFT>::TlsPhdr->p_memsz;
 244   case R_RELAX_TLS_GD_TO_LE_NEG:
 245   case R_NEG_TLS:
 246     return Out<ELF32LE>::TlsPhdr->p_memsz - Body.getVA<ELFT>(A);
 247   case R_ABS:
 248   case R_RELAX_GOT_PC_NOPIC:
 249     return Body.getVA<ELFT>(A);
 250   case R_GOT_OFF:
 251     return Body.getGotOffset<ELFT>() + A;
 252   case R_MIPS_GOT_LOCAL_PAGE:
 253     // If relocation against MIPS local symbol requires GOT entry, this entry
 254     // should be initialized by 'page address'. This address is high 16-bits
 255     // of sum the symbol's value and the addend.
 256     return Out<ELFT>::Got->getMipsLocalPageOffset(Body.getVA<ELFT>(A));
 257   case R_MIPS_GOT_OFF:
 258     // In case of MIPS if a GOT relocation has non-zero addend this addend
 259     // should be applied to the GOT entry content not to the GOT entry offset.
 260     // That is why we use separate expression type.
 261     return Out<ELFT>::Got->getMipsGotOffset(Body, A);
 262   case R_MIPS_TLSGD:
 263     return Out<ELFT>::Got->getGlobalDynOffset(Body) +
 264            Out<ELFT>::Got->getMipsTlsOffset() - MipsGPOffset;
 265   case R_MIPS_TLSLD:
 266     return Out<ELFT>::Got->getTlsIndexOff() +
 267            Out<ELFT>::Got->getMipsTlsOffset() - MipsGPOffset;
 268   case R_PPC_OPD: {
 269     uint64_t SymVA = Body.getVA<ELFT>(A);
 270     // If we have an undefined weak symbol, we might get here with a symbol
 271     // address of zero. That could overflow, but the code must be unreachable,
 272     // so don't bother doing anything at all.
 273     if (!SymVA)
 274       return 0;
 275     if (Out<ELF64BE>::Opd) {
 276       // If this is a local call, and we currently have the address of a
 277       // function-descriptor, get the underlying code address instead.
 278       uint64_t OpdStart = Out<ELF64BE>::Opd->getVA();
 279       uint64_t OpdEnd = OpdStart + Out<ELF64BE>::Opd->getSize();
 280       bool InOpd = OpdStart <= SymVA && SymVA < OpdEnd;
 281       if (InOpd)
 282         SymVA = read64be(&Out<ELF64BE>::OpdBuf[SymVA - OpdStart]);
 283     }
 284     return SymVA - P;
 285   }
 286   case R_PC:
 287   case R_RELAX_GOT_PC:
 288     return Body.getVA<ELFT>(A) - P;
 289   case R_PLT_PAGE_PC:
 290   case R_PAGE_PC:
 291     return getAArch64Page(Body.getVA<ELFT>(A)) - getAArch64Page(P);
 292   }
 293   llvm_unreachable("Invalid expression");
 294 }
 295
 296 // This function applies relocations to sections without SHF_ALLOC bit.
 297 // Such sections are never mapped to memory at runtime. Debug sections are
 298 // an example. Relocations in non-alloc sections are much easier to
 299 // handle than in allocated sections because it will never need complex
 300 // treatement such as GOT or PLT (because at runtime no one refers them).
 301 // So, we handle relocations for non-alloc sections directly in this
 302 // function as a performance optimization.
 303 template <class ELFT>
 304 template <class RelTy>
 305 void InputSection<ELFT>::relocateNonAlloc(uint8_t *Buf, ArrayRef<RelTy> Rels) {
 306   const unsigned Bits = sizeof(uintX_t) * 8;
 307   for (const RelTy &Rel : Rels) {
 308     uint32_t Type = Rel.getType(Config->Mips64EL);
 309     uintX_t Offset = this->getOffset(Rel.r_offset);
 310     uint8_t *BufLoc = Buf + Offset;
 311     uintX_t Addend = getAddend<ELFT>(Rel);
 312     if (!RelTy::IsRela)
 313       Addend += Target->getImplicitAddend(BufLoc, Type);
 314
 315     SymbolBody &Sym = this->File->getRelocTargetSym(Rel);
 316     if (Target->getRelExpr(Type, Sym) != R_ABS) {
 317       error(this->getSectionName() + " has non-ABS reloc");
 318       return;
 319     }
 320
 321     uintX_t AddrLoc = this->OutSec->getVA() + Offset;
 322     uint64_t SymVA =
 323         SignExtend64<Bits>(getSymVA<ELFT>(Type, Addend, AddrLoc, Sym, R_ABS));
 324     Target->relocateOne(BufLoc, Type, SymVA);
 325   }
 326 }
 327
 328 template <class ELFT>
 329 void InputSectionBase<ELFT>::relocate(uint8_t *Buf, uint8_t *BufEnd) {
 330   // scanReloc function in Writer.cpp constructs Relocations
 331   // vector only for SHF_ALLOC'ed sections. For other sections,
 332   // we handle relocations directly here.
 333   auto *IS = dyn_cast<InputSection<ELFT>>(this);
 334   if (IS && !(IS->Header->sh_flags & SHF_ALLOC)) {
 335     for (const Elf_Shdr *RelSec : IS->RelocSections) {
 336       if (RelSec->sh_type == SHT_RELA)
 337         IS->relocateNonAlloc(Buf, IS->File->getObj().relas(RelSec));
 338       else
 339         IS->relocateNonAlloc(Buf, IS->File->getObj().rels(RelSec));
 340     }
 341     return;
 342   }
 343
 344   const unsigned Bits = sizeof(uintX_t) * 8;
 345   for (const Relocation<ELFT> &Rel : Relocations) {
 346     uintX_t Offset = Rel.InputSec->getOffset(Rel.Offset);
 347     uint8_t *BufLoc = Buf + Offset;
 348     uint32_t Type = Rel.Type;
 349     uintX_t A = Rel.Addend;
 350
 351     uintX_t AddrLoc = OutSec->getVA() + Offset;
 352     RelExpr Expr = Rel.Expr;
 353     uint64_t SymVA =
 354         SignExtend64<Bits>(getSymVA<ELFT>(Type, A, AddrLoc, *Rel.Sym, Expr));
 355
 356     switch (Expr) {
 357     case R_RELAX_GOT_PC:
 358     case R_RELAX_GOT_PC_NOPIC:
 359       Target->relaxGot(BufLoc, SymVA);
 360       break;
 361     case R_RELAX_TLS_IE_TO_LE:
 362       Target->relaxTlsIeToLe(BufLoc, Type, SymVA);
 363       break;
 364     case R_RELAX_TLS_LD_TO_LE:
 365       Target->relaxTlsLdToLe(BufLoc, Type, SymVA);
 366       break;
 367     case R_RELAX_TLS_GD_TO_LE:
 368     case R_RELAX_TLS_GD_TO_LE_NEG:
 369       Target->relaxTlsGdToLe(BufLoc, Type, SymVA);
 370       break;
 371     case R_RELAX_TLS_GD_TO_IE:
 372     case R_RELAX_TLS_GD_TO_IE_ABS:
 373     case R_RELAX_TLS_GD_TO_IE_PAGE_PC:
 374     case R_RELAX_TLS_GD_TO_IE_END:
 375       Target->relaxTlsGdToIe(BufLoc, Type, SymVA);
 376       break;
 377     case R_PPC_PLT_OPD:
 378       // Patch a nop (0x60000000) to a ld.
 379       if (BufLoc + 8 <= BufEnd && read32be(BufLoc + 4) == 0x60000000)
 380         write32be(BufLoc + 4, 0xe8410028); // ld %r2, 40(%r1)
 381       // fallthrough
 382     default:
 383       Target->relocateOne(BufLoc, Type, SymVA);
 384       break;
 385     }
 386   }
 387 }
 388
 389 template <class ELFT> void InputSection<ELFT>::writeTo(uint8_t *Buf) {
 390   if (this->Header->sh_type == SHT_NOBITS)
 391     return;
 392   ELFFile<ELFT> &EObj = this->File->getObj();
 393
 394   // If -r is given, then an InputSection may be a relocation section.
 395   if (this->Header->sh_type == SHT_RELA) {
 396     copyRelocations(Buf + OutSecOff, EObj.relas(this->Header));
 397     return;
 398   }
 399   if (this->Header->sh_type == SHT_REL) {
 400     copyRelocations(Buf + OutSecOff, EObj.rels(this->Header));
 401     return;
 402   }
 403
 404   // Copy section contents from source object file to output file.
 405   ArrayRef<uint8_t> Data = this->getSectionData();
 406   memcpy(Buf + OutSecOff, Data.data(), Data.size());
 407
 408   // Iterate over all relocation sections that apply to this section.
 409   uint8_t *BufEnd = Buf + OutSecOff + Data.size();
 410   this->relocate(Buf, BufEnd);
 411
 412   // The section might have a data/code generated by the linker and need
 413   // to be written after the section. Usually these are thunks - small piece
 414   // of code used to jump between "incompatible" functions like PIC and non-PIC
 415   // or if the jump target too far and its address does not fit to the short
 416   // jump istruction.
 417   if (!Thunks.empty()) {
 418     Buf += OutSecOff + getThunkOff();
 419     for (const Thunk<ELFT> *T : Thunks) {
 420       T->writeTo(Buf);
 421       Buf += T->size();
 422     }
 423   }
 424 }
 425
 426 template <class ELFT>
 427 void InputSection<ELFT>::replace(InputSection<ELFT> *Other) {
 428   this->Alignment = std::max(this->Alignment, Other->Alignment);
 429   Other->Repl = this->Repl;
 430   Other->Live = false;
 431 }
 432
 433 template <class ELFT>
 434 SplitInputSection<ELFT>::SplitInputSection(
 435     elf::ObjectFile<ELFT> *File, const Elf_Shdr *Header,
 436     typename InputSectionBase<ELFT>::Kind SectionKind)
 437     : InputSectionBase<ELFT>(File, Header, SectionKind) {}
 438
 439 template <class ELFT>
 440 EhInputSection<ELFT>::EhInputSection(elf::ObjectFile<ELFT> *F,
 441                                      const Elf_Shdr *Header)
 442     : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::EHFrame) {
 443   // Mark .eh_frame sections as live by default because there are
 444   // usually no relocations that point to .eh_frames. Otherwise,
 445   // the garbage collector would drop all .eh_frame sections.
 446   this->Live = true;
 447 }
 448
 449 template <class ELFT>
 450 bool EhInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
 451   return S->SectionKind == InputSectionBase<ELFT>::EHFrame;
 452 }
 453
 454 // .eh_frame is a sequence of CIE or FDE records.
 455 // This function splits an input section into records and returns them.
 456 template <class ELFT>
 457 void EhInputSection<ELFT>::split() {
 458   ArrayRef<uint8_t> Data = this->getSectionData();
 459   for (size_t Off = 0, End = Data.size(); Off != End;) {
 460     size_t Size = readEhRecordSize<ELFT>(Data.slice(Off));
 461     this->Pieces.emplace_back(Off, Data.slice(Off, Size));
 462     // The empty record is the end marker.
 463     if (Size == 4)
 464       break;
 465     Off += Size;
 466   }
 467 }
 468
 469 template <class ELFT>
 470 typename ELFT::uint EhInputSection<ELFT>::getOffset(uintX_t Offset) const {
 471   // The file crtbeginT.o has relocations pointing to the start of an empty
 472   // .eh_frame that is known to be the first in the link. It does that to
 473   // identify the start of the output .eh_frame. Handle this special case.
 474   if (this->getSectionHdr()->sh_size == 0)
 475     return Offset;
 476   const SectionPiece *Piece = this->getSectionPiece(Offset);
 477   if (Piece->OutputOff == size_t(-1))
 478     return -1; // Not in the output
 479
 480   uintX_t Addend = Offset - Piece->InputOff;
 481   return Piece->OutputOff + Addend;
 482 }
 483
 484 static size_t findNull(ArrayRef<uint8_t> A, size_t EntSize) {
 485   // Optimize the common case.
 486   StringRef S((const char *)A.data(), A.size());
 487   if (EntSize == 1)
 488     return S.find(0);
 489
 490   for (unsigned I = 0, N = S.size(); I != N; I += EntSize) {
 491     const char *B = S.begin() + I;
 492     if (std::all_of(B, B + EntSize, [](char C) { return C == 0; }))
 493       return I;
 494   }
 495   return StringRef::npos;
 496 }
 497
 498 // Split SHF_STRINGS section. Such section is a sequence of
 499 // null-terminated strings.
 500 static std::vector<SectionPiece> splitStrings(ArrayRef<uint8_t> Data,
 501                                               size_t EntSize) {
 502   std::vector<SectionPiece> V;
 503   size_t Off = 0;
 504   while (!Data.empty()) {
 505     size_t End = findNull(Data, EntSize);
 506     if (End == StringRef::npos)
 507       fatal("string is not null terminated");
 508     size_t Size = End + EntSize;
 509     V.emplace_back(Off, Data.slice(0, Size));
 510     Data = Data.slice(Size);
 511     Off += Size;
 512   }
 513   return V;
 514 }
 515
 516 // Split non-SHF_STRINGS section. Such section is a sequence of
 517 // fixed size records.
 518 static std::vector<SectionPiece> splitNonStrings(ArrayRef<uint8_t> Data,
 519                                                  size_t EntSize) {
 520   std::vector<SectionPiece> V;
 521   size_t Size = Data.size();
 522   assert((Size % EntSize) == 0);
 523   for (unsigned I = 0, N = Size; I != N; I += EntSize)
 524     V.emplace_back(I, Data.slice(I, EntSize));
 525   return V;
 526 }
 527
 528 template <class ELFT>
 529 MergeInputSection<ELFT>::MergeInputSection(elf::ObjectFile<ELFT> *F,
 530                                            const Elf_Shdr *Header)
 531     : SplitInputSection<ELFT>(F, Header, InputSectionBase<ELFT>::Merge) {}
 532
 533 template <class ELFT> void MergeInputSection<ELFT>::splitIntoPieces() {
 534   ArrayRef<uint8_t> Data = this->getSectionData();
 535   uintX_t EntSize = this->Header->sh_entsize;
 536   if (this->Header->sh_flags & SHF_STRINGS)
 537     this->Pieces = splitStrings(Data, EntSize);
 538   else
 539     this->Pieces = splitNonStrings(Data, EntSize);
 540
 541   if (Config->GcSections)
 542     for (uintX_t Off : LiveOffsets)
 543       this->getSectionPiece(Off)->Live = true;
 544 }
 545
 546 template <class ELFT>
 547 bool MergeInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
 548   return S->SectionKind == InputSectionBase<ELFT>::Merge;
 549 }
 550
 551 // Do binary search to get a section piece at a given input offset.
 552 template <class ELFT>
 553 SectionPiece *SplitInputSection<ELFT>::getSectionPiece(uintX_t Offset) {
 554   auto *This = static_cast<const SplitInputSection<ELFT> *>(this);
 555   return const_cast<SectionPiece *>(This->getSectionPiece(Offset));
 556 }
 557
 558 template <class ELFT>
 559 const SectionPiece *
 560 SplitInputSection<ELFT>::getSectionPiece(uintX_t Offset) const {
 561   ArrayRef<uint8_t> D = this->getSectionData();
 562   StringRef Data((const char *)D.data(), D.size());
 563   uintX_t Size = Data.size();
 564   if (Offset >= Size)
 565     fatal("entry is past the end of the section");
 566
 567   // Find the element this offset points to.
 568   auto I = std::upper_bound(
 569       Pieces.begin(), Pieces.end(), Offset,
 570       [](const uintX_t &A, const SectionPiece &B) { return A < B.InputOff; });
 571   --I;
 572   return &*I;
 573 }
 574
 575 // Returns the offset in an output section for a given input offset.
 576 // Because contents of a mergeable section is not contiguous in output,
 577 // it is not just an addition to a base output offset.
 578 template <class ELFT>
 579 typename ELFT::uint MergeInputSection<ELFT>::getOffset(uintX_t Offset) const {
 580   auto It = OffsetMap.find(Offset);
 581   if (It != OffsetMap.end())
 582     return It->second;
 583
 584   // If Offset is not at beginning of a section piece, it is not in the map.
 585   // In that case we need to search from the original section piece vector.
 586   const SectionPiece &Piece = *this->getSectionPiece(Offset);
 587   assert(Piece.Live);
 588   uintX_t Addend = Offset - Piece.InputOff;
 589   return Piece.OutputOff + Addend;
 590 }
 591
 592 // Create a map from input offsets to output offsets for all section pieces.
 593 // It is called after finalize().
 594 template <class ELFT> void  MergeInputSection<ELFT>::finalizePieces() {
 595   OffsetMap.grow(this->Pieces.size());
 596   for (SectionPiece &Piece : this->Pieces) {
 597     if (!Piece.Live)
 598       continue;
 599     if (Piece.OutputOff == size_t(-1)) {
 600       // Offsets of tail-merged strings are computed lazily.
 601       auto *OutSec = static_cast<MergeOutputSection<ELFT> *>(this->OutSec);
 602       ArrayRef<uint8_t> D = Piece.data();
 603       StringRef S((const char *)D.data(), D.size());
 604       Piece.OutputOff = OutSec->getOffset(S);
 605     }
 606     OffsetMap[Piece.InputOff] = Piece.OutputOff;
 607   }
 608 }
 609
 610 template <class ELFT>
 611 MipsReginfoInputSection<ELFT>::MipsReginfoInputSection(elf::ObjectFile<ELFT> *F,
 612                                                        const Elf_Shdr *Hdr)
 613     : InputSectionBase<ELFT>(F, Hdr, InputSectionBase<ELFT>::MipsReginfo) {
 614   // Initialize this->Reginfo.
 615   ArrayRef<uint8_t> D = this->getSectionData();
 616   if (D.size() != sizeof(Elf_Mips_RegInfo<ELFT>)) {
 617     error("invalid size of .reginfo section");
 618     return;
 619   }
 620   Reginfo = reinterpret_cast<const Elf_Mips_RegInfo<ELFT> *>(D.data());
 621 }
 622
 623 template <class ELFT>
 624 bool MipsReginfoInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
 625   return S->SectionKind == InputSectionBase<ELFT>::MipsReginfo;
 626 }
 627
 628 template <class ELFT>
 629 MipsOptionsInputSection<ELFT>::MipsOptionsInputSection(elf::ObjectFile<ELFT> *F,
 630                                                        const Elf_Shdr *Hdr)
 631     : InputSectionBase<ELFT>(F, Hdr, InputSectionBase<ELFT>::MipsOptions) {
 632   // Find ODK_REGINFO option in the section's content.
 633   ArrayRef<uint8_t> D = this->getSectionData();
 634   while (!D.empty()) {
 635     if (D.size() < sizeof(Elf_Mips_Options<ELFT>)) {
 636       error("invalid size of .MIPS.options section");
 637       break;
 638     }
 639     auto *O = reinterpret_cast<const Elf_Mips_Options<ELFT> *>(D.data());
 640     if (O->kind == ODK_REGINFO) {
 641       Reginfo = &O->getRegInfo();
 642       break;
 643     }
 644     D = D.slice(O->size);
 645   }
 646 }
 647
 648 template <class ELFT>
 649 bool MipsOptionsInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
 650   return S->SectionKind == InputSectionBase<ELFT>::MipsOptions;
 651 }
 652
 653 template bool elf::isDiscarded<ELF32LE>(InputSectionBase<ELF32LE> *);
 654 template bool elf::isDiscarded<ELF32BE>(InputSectionBase<ELF32BE> *);
 655 template bool elf::isDiscarded<ELF64LE>(InputSectionBase<ELF64LE> *);
 656 template bool elf::isDiscarded<ELF64BE>(InputSectionBase<ELF64BE> *);
 657
 658 template class elf::InputSectionBase<ELF32LE>;
 659 template class elf::InputSectionBase<ELF32BE>;
 660 template class elf::InputSectionBase<ELF64LE>;
 661 template class elf::InputSectionBase<ELF64BE>;
 662
 663 template class elf::InputSection<ELF32LE>;
 664 template class elf::InputSection<ELF32BE>;
 665 template class elf::InputSection<ELF64LE>;
 666 template class elf::InputSection<ELF64BE>;
 667
 668 template class elf::SplitInputSection<ELF32LE>;
 669 template class elf::SplitInputSection<ELF32BE>;
 670 template class elf::SplitInputSection<ELF64LE>;
 671 template class elf::SplitInputSection<ELF64BE>;
 672
 673 template class elf::EhInputSection<ELF32LE>;
 674 template class elf::EhInputSection<ELF32BE>;
 675 template class elf::EhInputSection<ELF64LE>;
 676 template class elf::EhInputSection<ELF64BE>;
 677
 678 template class elf::MergeInputSection<ELF32LE>;
 679 template class elf::MergeInputSection<ELF32BE>;
 680 template class elf::MergeInputSection<ELF64LE>;
 681 template class elf::MergeInputSection<ELF64BE>;
 682
 683 template class elf::MipsReginfoInputSection<ELF32LE>;
 684 template class elf::MipsReginfoInputSection<ELF32BE>;
 685 template class elf::MipsReginfoInputSection<ELF64LE>;
 686 template class elf::MipsReginfoInputSection<ELF64BE>;
 687
 688 template class elf::MipsOptionsInputSection<ELF32LE>;
 689 template class elf::MipsOptionsInputSection<ELF32BE>;
 690 template class elf::MipsOptionsInputSection<ELF64LE>;
 691 template class elf::MipsOptionsInputSection<ELF64BE>;