contrib/llvm-project/lld/ELF/OutputSections.cpp

   1 //===- OutputSections.cpp -------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "OutputSections.h"
  10 #include "Config.h"
  11 #include "LinkerScript.h"
  12 #include "SymbolTable.h"
  13 #include "SyntheticSections.h"
  14 #include "Target.h"
  15 #include "lld/Common/Memory.h"
  16 #include "lld/Common/Strings.h"
  17 #include "lld/Common/Threads.h"
  18 #include "llvm/BinaryFormat/Dwarf.h"
  19 #include "llvm/Support/Compression.h"
  20 #include "llvm/Support/MD5.h"
  21 #include "llvm/Support/MathExtras.h"
  22 #include "llvm/Support/SHA1.h"
  23
  24 using namespace llvm;
  25 using namespace llvm::dwarf;
  26 using namespace llvm::object;
  27 using namespace llvm::support::endian;
  28 using namespace llvm::ELF;
  29
  30 namespace lld {
  31 namespace elf {
  32 uint8_t *Out::bufferStart;
  33 uint8_t Out::first;
  34 PhdrEntry *Out::tlsPhdr;
  35 OutputSection *Out::elfHeader;
  36 OutputSection *Out::programHeaders;
  37 OutputSection *Out::preinitArray;
  38 OutputSection *Out::initArray;
  39 OutputSection *Out::finiArray;
  40
  41 std::vector<OutputSection *> outputSections;
  42
  43 uint32_t OutputSection::getPhdrFlags() const {
  44   uint32_t ret = 0;
  45   if (config->emachine != EM_ARM || !(flags & SHF_ARM_PURECODE))
  46     ret |= PF_R;
  47   if (flags & SHF_WRITE)
  48     ret |= PF_W;
  49   if (flags & SHF_EXECINSTR)
  50     ret |= PF_X;
  51   return ret;
  52 }
  53
  54 template <class ELFT>
  55 void OutputSection::writeHeaderTo(typename ELFT::Shdr *shdr) {
  56   shdr->sh_entsize = entsize;
  57   shdr->sh_addralign = alignment;
  58   shdr->sh_type = type;
  59   shdr->sh_offset = offset;
  60   shdr->sh_flags = flags;
  61   shdr->sh_info = info;
  62   shdr->sh_link = link;
  63   shdr->sh_addr = addr;
  64   shdr->sh_size = size;
  65   shdr->sh_name = shName;
  66 }
  67
  68 OutputSection::OutputSection(StringRef name, uint32_t type, uint64_t flags)
  69     : BaseCommand(OutputSectionKind),
  70       SectionBase(Output, name, flags, /*Entsize*/ 0, /*Alignment*/ 1, type,
  71                   /*Info*/ 0, /*Link*/ 0) {}
  72
  73 // We allow sections of types listed below to merged into a
  74 // single progbits section. This is typically done by linker
  75 // scripts. Merging nobits and progbits will force disk space
  76 // to be allocated for nobits sections. Other ones don't require
  77 // any special treatment on top of progbits, so there doesn't
  78 // seem to be a harm in merging them.
  79 static bool canMergeToProgbits(unsigned type) {
  80   return type == SHT_NOBITS || type == SHT_PROGBITS || type == SHT_INIT_ARRAY ||
  81          type == SHT_PREINIT_ARRAY || type == SHT_FINI_ARRAY ||
  82          type == SHT_NOTE;
  83 }
  84
  85 // Record that isec will be placed in the OutputSection. isec does not become
  86 // permanent until finalizeInputSections() is called. The function should not be
  87 // used after finalizeInputSections() is called. If you need to add an
  88 // InputSection post finalizeInputSections(), then you must do the following:
  89 //
  90 // 1. Find or create an InputSectionDescription to hold InputSection.
  91 // 2. Add the InputSection to the InputSectionDesciption::sections.
  92 // 3. Call commitSection(isec).
  93 void OutputSection::recordSection(InputSectionBase *isec) {
  94   partition = isec->partition;
  95   isec->parent = this;
  96   if (sectionCommands.empty() ||
  97       !isa<InputSectionDescription>(sectionCommands.back()))
  98     sectionCommands.push_back(make<InputSectionDescription>(""));
  99   auto *isd = cast<InputSectionDescription>(sectionCommands.back());
 100   isd->sectionBases.push_back(isec);
 101 }
 102
 103 // Update fields (type, flags, alignment, etc) according to the InputSection
 104 // isec. Also check whether the InputSection flags and type are consistent with
 105 // other InputSections.
 106 void OutputSection::commitSection(InputSection *isec) {
 107   if (!hasInputSections) {
 108     // If IS is the first section to be added to this section,
 109     // initialize type, entsize and flags from isec.
 110     hasInputSections = true;
 111     type = isec->type;
 112     entsize = isec->entsize;
 113     flags = isec->flags;
 114   } else {
 115     // Otherwise, check if new type or flags are compatible with existing ones.
 116     unsigned mask = SHF_TLS | SHF_LINK_ORDER;
 117     if ((flags & mask) != (isec->flags & mask))
 118       error("incompatible section flags for " + name + "\n>>> " + toString(isec) +
 119             ": 0x" + utohexstr(isec->flags) + "\n>>> output section " + name +
 120             ": 0x" + utohexstr(flags));
 121
 122     if (type != isec->type) {
 123       if (!canMergeToProgbits(type) || !canMergeToProgbits(isec->type))
 124         error("section type mismatch for " + isec->name + "\n>>> " +
 125               toString(isec) + ": " +
 126               getELFSectionTypeName(config->emachine, isec->type) +
 127               "\n>>> output section " + name + ": " +
 128               getELFSectionTypeName(config->emachine, type));
 129       type = SHT_PROGBITS;
 130     }
 131   }
 132   if (noload)
 133     type = SHT_NOBITS;
 134
 135   isec->parent = this;
 136   uint64_t andMask =
 137       config->emachine == EM_ARM ? (uint64_t)SHF_ARM_PURECODE : 0;
 138   uint64_t orMask = ~andMask;
 139   uint64_t andFlags = (flags & isec->flags) & andMask;
 140   uint64_t orFlags = (flags | isec->flags) & orMask;
 141   flags = andFlags | orFlags;
 142   if (nonAlloc)
 143     flags &= ~(uint64_t)SHF_ALLOC;
 144
 145   alignment = std::max(alignment, isec->alignment);
 146
 147   // If this section contains a table of fixed-size entries, sh_entsize
 148   // holds the element size. If it contains elements of different size we
 149   // set sh_entsize to 0.
 150   if (entsize != isec->entsize)
 151     entsize = 0;
 152 }
 153
 154 // This function scans over the InputSectionBase list sectionBases to create
 155 // InputSectionDescription::sections.
 156 //
 157 // It removes MergeInputSections from the input section array and adds
 158 // new synthetic sections at the location of the first input section
 159 // that it replaces. It then finalizes each synthetic section in order
 160 // to compute an output offset for each piece of each input section.
 161 void OutputSection::finalizeInputSections() {
 162   std::vector<MergeSyntheticSection *> mergeSections;
 163   for (BaseCommand *base : sectionCommands) {
 164     auto *cmd = dyn_cast<InputSectionDescription>(base);
 165     if (!cmd)
 166       continue;
 167     cmd->sections.reserve(cmd->sectionBases.size());
 168     for (InputSectionBase *s : cmd->sectionBases) {
 169       MergeInputSection *ms = dyn_cast<MergeInputSection>(s);
 170       if (!ms) {
 171         cmd->sections.push_back(cast<InputSection>(s));
 172         continue;
 173       }
 174
 175       // We do not want to handle sections that are not alive, so just remove
 176       // them instead of trying to merge.
 177       if (!ms->isLive())
 178         continue;
 179
 180       auto i = llvm::find_if(mergeSections, [=](MergeSyntheticSection *sec) {
 181         // While we could create a single synthetic section for two different
 182         // values of Entsize, it is better to take Entsize into consideration.
 183         //
 184         // With a single synthetic section no two pieces with different Entsize
 185         // could be equal, so we may as well have two sections.
 186         //
 187         // Using Entsize in here also allows us to propagate it to the synthetic
 188         // section.
 189         //
 190         // SHF_STRINGS section with different alignments should not be merged.
 191         return sec->flags == ms->flags && sec->entsize == ms->entsize &&
 192                (sec->alignment == ms->alignment || !(sec->flags & SHF_STRINGS));
 193       });
 194       if (i == mergeSections.end()) {
 195         MergeSyntheticSection *syn =
 196             createMergeSynthetic(name, ms->type, ms->flags, ms->alignment);
 197         mergeSections.push_back(syn);
 198         i = std::prev(mergeSections.end());
 199         syn->entsize = ms->entsize;
 200         cmd->sections.push_back(syn);
 201       }
 202       (*i)->addSection(ms);
 203     }
 204
 205     // sectionBases should not be used from this point onwards. Clear it to
 206     // catch misuses.
 207     cmd->sectionBases.clear();
 208
 209     // Some input sections may be removed from the list after ICF.
 210     for (InputSection *s : cmd->sections)
 211       commitSection(s);
 212   }
 213   for (auto *ms : mergeSections)
 214     ms->finalizeContents();
 215 }
 216
 217 static void sortByOrder(MutableArrayRef<InputSection *> in,
 218                         llvm::function_ref<int(InputSectionBase *s)> order) {
 219   std::vector<std::pair<int, InputSection *>> v;
 220   for (InputSection *s : in)
 221     v.push_back({order(s), s});
 222   llvm::stable_sort(v, less_first());
 223
 224   for (size_t i = 0; i < v.size(); ++i)
 225     in[i] = v[i].second;
 226 }
 227
 228 uint64_t getHeaderSize() {
 229   if (config->oFormatBinary)
 230     return 0;
 231   return Out::elfHeader->size + Out::programHeaders->size;
 232 }
 233
 234 bool OutputSection::classof(const BaseCommand *c) {
 235   return c->kind == OutputSectionKind;
 236 }
 237
 238 void OutputSection::sort(llvm::function_ref<int(InputSectionBase *s)> order) {
 239   assert(isLive());
 240   for (BaseCommand *b : sectionCommands)
 241     if (auto *isd = dyn_cast<InputSectionDescription>(b))
 242       sortByOrder(isd->sections, order);
 243 }
 244
 245 // Fill [Buf, Buf + Size) with Filler.
 246 // This is used for linker script "=fillexp" command.
 247 static void fill(uint8_t *buf, size_t size,
 248                  const std::array<uint8_t, 4> &filler) {
 249   size_t i = 0;
 250   for (; i + 4 < size; i += 4)
 251     memcpy(buf + i, filler.data(), 4);
 252   memcpy(buf + i, filler.data(), size - i);
 253 }
 254
 255 // Compress section contents if this section contains debug info.
 256 template <class ELFT> void OutputSection::maybeCompress() {
 257   using Elf_Chdr = typename ELFT::Chdr;
 258
 259   // Compress only DWARF debug sections.
 260   if (!config->compressDebugSections || (flags & SHF_ALLOC) ||
 261       !name.startswith(".debug_"))
 262     return;
 263
 264   // Create a section header.
 265   zDebugHeader.resize(sizeof(Elf_Chdr));
 266   auto *hdr = reinterpret_cast<Elf_Chdr *>(zDebugHeader.data());
 267   hdr->ch_type = ELFCOMPRESS_ZLIB;
 268   hdr->ch_size = size;
 269   hdr->ch_addralign = alignment;
 270
 271   // Write section contents to a temporary buffer and compress it.
 272   std::vector<uint8_t> buf(size);
 273   writeTo<ELFT>(buf.data());
 274   if (Error e = zlib::compress(toStringRef(buf), compressedData))
 275     fatal("compress failed: " + llvm::toString(std::move(e)));
 276
 277   // Update section headers.
 278   size = sizeof(Elf_Chdr) + compressedData.size();
 279   flags |= SHF_COMPRESSED;
 280 }
 281
 282 static void writeInt(uint8_t *buf, uint64_t data, uint64_t size) {
 283   if (size == 1)
 284     *buf = data;
 285   else if (size == 2)
 286     write16(buf, data);
 287   else if (size == 4)
 288     write32(buf, data);
 289   else if (size == 8)
 290     write64(buf, data);
 291   else
 292     llvm_unreachable("unsupported Size argument");
 293 }
 294
 295 template <class ELFT> void OutputSection::writeTo(uint8_t *buf) {
 296   if (type == SHT_NOBITS)
 297     return;
 298
 299   // If -compress-debug-section is specified and if this is a debug seciton,
 300   // we've already compressed section contents. If that's the case,
 301   // just write it down.
 302   if (!compressedData.empty()) {
 303     memcpy(buf, zDebugHeader.data(), zDebugHeader.size());
 304     memcpy(buf + zDebugHeader.size(), compressedData.data(),
 305            compressedData.size());
 306     return;
 307   }
 308
 309   // Write leading padding.
 310   std::vector<InputSection *> sections = getInputSections(this);
 311   std::array<uint8_t, 4> filler = getFiller();
 312   bool nonZeroFiller = read32(filler.data()) != 0;
 313   if (nonZeroFiller)
 314     fill(buf, sections.empty() ? size : sections[0]->outSecOff, filler);
 315
 316   parallelForEachN(0, sections.size(), [&](size_t i) {
 317     InputSection *isec = sections[i];
 318     isec->writeTo<ELFT>(buf);
 319
 320     // Fill gaps between sections.
 321     if (nonZeroFiller) {
 322       uint8_t *start = buf + isec->outSecOff + isec->getSize();
 323       uint8_t *end;
 324       if (i + 1 == sections.size())
 325         end = buf + size;
 326       else
 327         end = buf + sections[i + 1]->outSecOff;
 328       fill(start, end - start, filler);
 329     }
 330   });
 331
 332   // Linker scripts may have BYTE()-family commands with which you
 333   // can write arbitrary bytes to the output. Process them if any.
 334   for (BaseCommand *base : sectionCommands)
 335     if (auto *data = dyn_cast<ByteCommand>(base))
 336       writeInt(buf + data->offset, data->expression().getValue(), data->size);
 337 }
 338
 339 static void finalizeShtGroup(OutputSection *os,
 340                              InputSection *section) {
 341   assert(config->relocatable);
 342
 343   // sh_link field for SHT_GROUP sections should contain the section index of
 344   // the symbol table.
 345   os->link = in.symTab->getParent()->sectionIndex;
 346
 347   // sh_info then contain index of an entry in symbol table section which
 348   // provides signature of the section group.
 349   ArrayRef<Symbol *> symbols = section->file->getSymbols();
 350   os->info = in.symTab->getSymbolIndex(symbols[section->info]);
 351 }
 352
 353 void OutputSection::finalize() {
 354   std::vector<InputSection *> v = getInputSections(this);
 355   InputSection *first = v.empty() ? nullptr : v[0];
 356
 357   if (flags & SHF_LINK_ORDER) {
 358     // We must preserve the link order dependency of sections with the
 359     // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
 360     // need to translate the InputSection sh_link to the OutputSection sh_link,
 361     // all InputSections in the OutputSection have the same dependency.
 362     if (auto *ex = dyn_cast<ARMExidxSyntheticSection>(first))
 363       link = ex->getLinkOrderDep()->getParent()->sectionIndex;
 364     else if (auto *d = first->getLinkOrderDep())
 365       link = d->getParent()->sectionIndex;
 366   }
 367
 368   if (type == SHT_GROUP) {
 369     finalizeShtGroup(this, first);
 370     return;
 371   }
 372
 373   if (!config->copyRelocs || (type != SHT_RELA && type != SHT_REL))
 374     return;
 375
 376   if (isa<SyntheticSection>(first))
 377     return;
 378
 379   link = in.symTab->getParent()->sectionIndex;
 380   // sh_info for SHT_REL[A] sections should contain the section header index of
 381   // the section to which the relocation applies.
 382   InputSectionBase *s = first->getRelocatedSection();
 383   info = s->getOutputSection()->sectionIndex;
 384   flags |= SHF_INFO_LINK;
 385 }
 386
 387 // Returns true if S matches /Filename.?\.o$/.
 388 static bool isCrtBeginEnd(StringRef s, StringRef filename) {
 389   if (!s.endswith(".o"))
 390     return false;
 391   s = s.drop_back(2);
 392   if (s.endswith(filename))
 393     return true;
 394   return !s.empty() && s.drop_back().endswith(filename);
 395 }
 396
 397 static bool isCrtbegin(StringRef s) { return isCrtBeginEnd(s, "crtbegin"); }
 398 static bool isCrtend(StringRef s) { return isCrtBeginEnd(s, "crtend"); }
 399
 400 // .ctors and .dtors are sorted by this priority from highest to lowest.
 401 //
 402 //  1. The section was contained in crtbegin (crtbegin contains
 403 //     some sentinel value in its .ctors and .dtors so that the runtime
 404 //     can find the beginning of the sections.)
 405 //
 406 //  2. The section has an optional priority value in the form of ".ctors.N"
 407 //     or ".dtors.N" where N is a number. Unlike .{init,fini}_array,
 408 //     they are compared as string rather than number.
 409 //
 410 //  3. The section is just ".ctors" or ".dtors".
 411 //
 412 //  4. The section was contained in crtend, which contains an end marker.
 413 //
 414 // In an ideal world, we don't need this function because .init_array and
 415 // .ctors are duplicate features (and .init_array is newer.) However, there
 416 // are too many real-world use cases of .ctors, so we had no choice to
 417 // support that with this rather ad-hoc semantics.
 418 static bool compCtors(const InputSection *a, const InputSection *b) {
 419   bool beginA = isCrtbegin(a->file->getName());
 420   bool beginB = isCrtbegin(b->file->getName());
 421   if (beginA != beginB)
 422     return beginA;
 423   bool endA = isCrtend(a->file->getName());
 424   bool endB = isCrtend(b->file->getName());
 425   if (endA != endB)
 426     return endB;
 427   StringRef x = a->name;
 428   StringRef y = b->name;
 429   assert(x.startswith(".ctors") || x.startswith(".dtors"));
 430   assert(y.startswith(".ctors") || y.startswith(".dtors"));
 431   x = x.substr(6);
 432   y = y.substr(6);
 433   return x < y;
 434 }
 435
 436 // Sorts input sections by the special rules for .ctors and .dtors.
 437 // Unfortunately, the rules are different from the one for .{init,fini}_array.
 438 // Read the comment above.
 439 void OutputSection::sortCtorsDtors() {
 440   assert(sectionCommands.size() == 1);
 441   auto *isd = cast<InputSectionDescription>(sectionCommands[0]);
 442   llvm::stable_sort(isd->sections, compCtors);
 443 }
 444
 445 // If an input string is in the form of "foo.N" where N is a number,
 446 // return N. Otherwise, returns 65536, which is one greater than the
 447 // lowest priority.
 448 int getPriority(StringRef s) {
 449   size_t pos = s.rfind('.');
 450   if (pos == StringRef::npos)
 451     return 65536;
 452   int v;
 453   if (!to_integer(s.substr(pos + 1), v, 10))
 454     return 65536;
 455   return v;
 456 }
 457
 458 std::vector<InputSection *> getInputSections(OutputSection *os) {
 459   std::vector<InputSection *> ret;
 460   for (BaseCommand *base : os->sectionCommands)
 461     if (auto *isd = dyn_cast<InputSectionDescription>(base))
 462       ret.insert(ret.end(), isd->sections.begin(), isd->sections.end());
 463   return ret;
 464 }
 465
 466 // Sorts input sections by section name suffixes, so that .foo.N comes
 467 // before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
 468 // We want to keep the original order if the priorities are the same
 469 // because the compiler keeps the original initialization order in a
 470 // translation unit and we need to respect that.
 471 // For more detail, read the section of the GCC's manual about init_priority.
 472 void OutputSection::sortInitFini() {
 473   // Sort sections by priority.
 474   sort([](InputSectionBase *s) { return getPriority(s->name); });
 475 }
 476
 477 std::array<uint8_t, 4> OutputSection::getFiller() {
 478   if (filler)
 479     return *filler;
 480   if (flags & SHF_EXECINSTR)
 481     return target->trapInstr;
 482   return {0, 0, 0, 0};
 483 }
 484
 485 template void OutputSection::writeHeaderTo<ELF32LE>(ELF32LE::Shdr *Shdr);
 486 template void OutputSection::writeHeaderTo<ELF32BE>(ELF32BE::Shdr *Shdr);
 487 template void OutputSection::writeHeaderTo<ELF64LE>(ELF64LE::Shdr *Shdr);
 488 template void OutputSection::writeHeaderTo<ELF64BE>(ELF64BE::Shdr *Shdr);
 489
 490 template void OutputSection::writeTo<ELF32LE>(uint8_t *Buf);
 491 template void OutputSection::writeTo<ELF32BE>(uint8_t *Buf);
 492 template void OutputSection::writeTo<ELF64LE>(uint8_t *Buf);
 493 template void OutputSection::writeTo<ELF64BE>(uint8_t *Buf);
 494
 495 template void OutputSection::maybeCompress<ELF32LE>();
 496 template void OutputSection::maybeCompress<ELF32BE>();
 497 template void OutputSection::maybeCompress<ELF64LE>();
 498 template void OutputSection::maybeCompress<ELF64BE>();
 499
 500 } // namespace elf
 501 } // namespace lld