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 using namespace lld;
  31 using namespace lld::elf;
  32
  33 uint8_t *Out::bufferStart;
  34 uint8_t Out::first;
  35 PhdrEntry *Out::tlsPhdr;
  36 OutputSection *Out::elfHeader;
  37 OutputSection *Out::programHeaders;
  38 OutputSection *Out::preinitArray;
  39 OutputSection *Out::initArray;
  40 OutputSection *Out::finiArray;
  41
  42 std::vector<OutputSection *> elf::outputSections;
  43
  44 uint32_t OutputSection::getPhdrFlags() const {
  45   uint32_t ret = 0;
  46   if (config->emachine != EM_ARM || !(flags & SHF_ARM_PURECODE))
  47     ret |= PF_R;
  48   if (flags & SHF_WRITE)
  49     ret |= PF_W;
  50   if (flags & SHF_EXECINSTR)
  51     ret |= PF_X;
  52   return ret;
  53 }
  54
  55 template <class ELFT>
  56 void OutputSection::writeHeaderTo(typename ELFT::Shdr *shdr) {
  57   shdr->sh_entsize = entsize;
  58   shdr->sh_addralign = alignment;
  59   shdr->sh_type = type;
  60   shdr->sh_offset = offset;
  61   shdr->sh_flags = flags;
  62   shdr->sh_info = info;
  63   shdr->sh_link = link;
  64   shdr->sh_addr = addr;
  65   shdr->sh_size = size;
  66   shdr->sh_name = shName;
  67 }
  68
  69 OutputSection::OutputSection(StringRef name, uint32_t type, uint64_t flags)
  70     : BaseCommand(OutputSectionKind),
  71       SectionBase(Output, name, flags, /*Entsize*/ 0, /*Alignment*/ 1, type,
  72                   /*Info*/ 0, /*Link*/ 0) {}
  73
  74 // We allow sections of types listed below to merged into a
  75 // single progbits section. This is typically done by linker
  76 // scripts. Merging nobits and progbits will force disk space
  77 // to be allocated for nobits sections. Other ones don't require
  78 // any special treatment on top of progbits, so there doesn't
  79 // seem to be a harm in merging them.
  80 static bool canMergeToProgbits(unsigned type) {
  81   return type == SHT_NOBITS || type == SHT_PROGBITS || type == SHT_INIT_ARRAY ||
  82          type == SHT_PREINIT_ARRAY || type == SHT_FINI_ARRAY ||
  83          type == SHT_NOTE;
  84 }
  85
  86 void OutputSection::addSection(InputSection *isec) {
  87   if (!hasInputSections) {
  88     // If IS is the first section to be added to this section,
  89     // initialize Partition, Type, Entsize and flags from IS.
  90     hasInputSections = true;
  91     partition = isec->partition;
  92     type = isec->type;
  93     entsize = isec->entsize;
  94     flags = isec->flags;
  95   } else {
  96     // Otherwise, check if new type or flags are compatible with existing ones.
  97     unsigned mask = SHF_TLS | SHF_LINK_ORDER;
  98     if ((flags & mask) != (isec->flags & mask))
  99       error("incompatible section flags for " + name + "\n>>> " + toString(isec) +
 100             ": 0x" + utohexstr(isec->flags) + "\n>>> output section " + name +
 101             ": 0x" + utohexstr(flags));
 102
 103     if (type != isec->type) {
 104       if (!canMergeToProgbits(type) || !canMergeToProgbits(isec->type))
 105         error("section type mismatch for " + isec->name + "\n>>> " +
 106               toString(isec) + ": " +
 107               getELFSectionTypeName(config->emachine, isec->type) +
 108               "\n>>> output section " + name + ": " +
 109               getELFSectionTypeName(config->emachine, type));
 110       type = SHT_PROGBITS;
 111     }
 112   }
 113
 114   isec->parent = this;
 115   uint64_t andMask =
 116       config->emachine == EM_ARM ? (uint64_t)SHF_ARM_PURECODE : 0;
 117   uint64_t orMask = ~andMask;
 118   uint64_t andFlags = (flags & isec->flags) & andMask;
 119   uint64_t orFlags = (flags | isec->flags) & orMask;
 120   flags = andFlags | orFlags;
 121
 122   alignment = std::max(alignment, isec->alignment);
 123
 124   // If this section contains a table of fixed-size entries, sh_entsize
 125   // holds the element size. If it contains elements of different size we
 126   // set sh_entsize to 0.
 127   if (entsize != isec->entsize)
 128     entsize = 0;
 129
 130   if (!isec->assigned) {
 131     isec->assigned = true;
 132     if (sectionCommands.empty() ||
 133         !isa<InputSectionDescription>(sectionCommands.back()))
 134       sectionCommands.push_back(make<InputSectionDescription>(""));
 135     auto *isd = cast<InputSectionDescription>(sectionCommands.back());
 136     isd->sections.push_back(isec);
 137   }
 138 }
 139
 140 static void sortByOrder(MutableArrayRef<InputSection *> in,
 141                         llvm::function_ref<int(InputSectionBase *s)> order) {
 142   std::vector<std::pair<int, InputSection *>> v;
 143   for (InputSection *s : in)
 144     v.push_back({order(s), s});
 145   llvm::stable_sort(v, less_first());
 146
 147   for (size_t i = 0; i < v.size(); ++i)
 148     in[i] = v[i].second;
 149 }
 150
 151 uint64_t elf::getHeaderSize() {
 152   if (config->oFormatBinary)
 153     return 0;
 154   return Out::elfHeader->size + Out::programHeaders->size;
 155 }
 156
 157 bool OutputSection::classof(const BaseCommand *c) {
 158   return c->kind == OutputSectionKind;
 159 }
 160
 161 void OutputSection::sort(llvm::function_ref<int(InputSectionBase *s)> order) {
 162   assert(isLive());
 163   for (BaseCommand *b : sectionCommands)
 164     if (auto *isd = dyn_cast<InputSectionDescription>(b))
 165       sortByOrder(isd->sections, order);
 166 }
 167
 168 // Fill [Buf, Buf + Size) with Filler.
 169 // This is used for linker script "=fillexp" command.
 170 static void fill(uint8_t *buf, size_t size,
 171                  const std::array<uint8_t, 4> &filler) {
 172   size_t i = 0;
 173   for (; i + 4 < size; i += 4)
 174     memcpy(buf + i, filler.data(), 4);
 175   memcpy(buf + i, filler.data(), size - i);
 176 }
 177
 178 // Compress section contents if this section contains debug info.
 179 template <class ELFT> void OutputSection::maybeCompress() {
 180   using Elf_Chdr = typename ELFT::Chdr;
 181
 182   // Compress only DWARF debug sections.
 183   if (!config->compressDebugSections || (flags & SHF_ALLOC) ||
 184       !name.startswith(".debug_"))
 185     return;
 186
 187   // Create a section header.
 188   zDebugHeader.resize(sizeof(Elf_Chdr));
 189   auto *hdr = reinterpret_cast<Elf_Chdr *>(zDebugHeader.data());
 190   hdr->ch_type = ELFCOMPRESS_ZLIB;
 191   hdr->ch_size = size;
 192   hdr->ch_addralign = alignment;
 193
 194   // Write section contents to a temporary buffer and compress it.
 195   std::vector<uint8_t> buf(size);
 196   writeTo<ELFT>(buf.data());
 197   if (Error e = zlib::compress(toStringRef(buf), compressedData))
 198     fatal("compress failed: " + llvm::toString(std::move(e)));
 199
 200   // Update section headers.
 201   size = sizeof(Elf_Chdr) + compressedData.size();
 202   flags |= SHF_COMPRESSED;
 203 }
 204
 205 static void writeInt(uint8_t *buf, uint64_t data, uint64_t size) {
 206   if (size == 1)
 207     *buf = data;
 208   else if (size == 2)
 209     write16(buf, data);
 210   else if (size == 4)
 211     write32(buf, data);
 212   else if (size == 8)
 213     write64(buf, data);
 214   else
 215     llvm_unreachable("unsupported Size argument");
 216 }
 217
 218 template <class ELFT> void OutputSection::writeTo(uint8_t *buf) {
 219   if (type == SHT_NOBITS)
 220     return;
 221
 222   // If -compress-debug-section is specified and if this is a debug seciton,
 223   // we've already compressed section contents. If that's the case,
 224   // just write it down.
 225   if (!compressedData.empty()) {
 226     memcpy(buf, zDebugHeader.data(), zDebugHeader.size());
 227     memcpy(buf + zDebugHeader.size(), compressedData.data(),
 228            compressedData.size());
 229     return;
 230   }
 231
 232   // Write leading padding.
 233   std::vector<InputSection *> sections = getInputSections(this);
 234   std::array<uint8_t, 4> filler = getFiller();
 235   bool nonZeroFiller = read32(filler.data()) != 0;
 236   if (nonZeroFiller)
 237     fill(buf, sections.empty() ? size : sections[0]->outSecOff, filler);
 238
 239   parallelForEachN(0, sections.size(), [&](size_t i) {
 240     InputSection *isec = sections[i];
 241     isec->writeTo<ELFT>(buf);
 242
 243     // Fill gaps between sections.
 244     if (nonZeroFiller) {
 245       uint8_t *start = buf + isec->outSecOff + isec->getSize();
 246       uint8_t *end;
 247       if (i + 1 == sections.size())
 248         end = buf + size;
 249       else
 250         end = buf + sections[i + 1]->outSecOff;
 251       fill(start, end - start, filler);
 252     }
 253   });
 254
 255   // Linker scripts may have BYTE()-family commands with which you
 256   // can write arbitrary bytes to the output. Process them if any.
 257   for (BaseCommand *base : sectionCommands)
 258     if (auto *data = dyn_cast<ByteCommand>(base))
 259       writeInt(buf + data->offset, data->expression().getValue(), data->size);
 260 }
 261
 262 static void finalizeShtGroup(OutputSection *os,
 263                              InputSection *section) {
 264   assert(config->relocatable);
 265
 266   // sh_link field for SHT_GROUP sections should contain the section index of
 267   // the symbol table.
 268   os->link = in.symTab->getParent()->sectionIndex;
 269
 270   // sh_info then contain index of an entry in symbol table section which
 271   // provides signature of the section group.
 272   ArrayRef<Symbol *> symbols = section->file->getSymbols();
 273   os->info = in.symTab->getSymbolIndex(symbols[section->info]);
 274 }
 275
 276 void OutputSection::finalize() {
 277   std::vector<InputSection *> v = getInputSections(this);
 278   InputSection *first = v.empty() ? nullptr : v[0];
 279
 280   if (flags & SHF_LINK_ORDER) {
 281     // We must preserve the link order dependency of sections with the
 282     // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
 283     // need to translate the InputSection sh_link to the OutputSection sh_link,
 284     // all InputSections in the OutputSection have the same dependency.
 285     if (auto *ex = dyn_cast<ARMExidxSyntheticSection>(first))
 286       link = ex->getLinkOrderDep()->getParent()->sectionIndex;
 287     else if (auto *d = first->getLinkOrderDep())
 288       link = d->getParent()->sectionIndex;
 289   }
 290
 291   if (type == SHT_GROUP) {
 292     finalizeShtGroup(this, first);
 293     return;
 294   }
 295
 296   if (!config->copyRelocs || (type != SHT_RELA && type != SHT_REL))
 297     return;
 298
 299   if (isa<SyntheticSection>(first))
 300     return;
 301
 302   link = in.symTab->getParent()->sectionIndex;
 303   // sh_info for SHT_REL[A] sections should contain the section header index of
 304   // the section to which the relocation applies.
 305   InputSectionBase *s = first->getRelocatedSection();
 306   info = s->getOutputSection()->sectionIndex;
 307   flags |= SHF_INFO_LINK;
 308 }
 309
 310 // Returns true if S matches /Filename.?\.o$/.
 311 static bool isCrtBeginEnd(StringRef s, StringRef filename) {
 312   if (!s.endswith(".o"))
 313     return false;
 314   s = s.drop_back(2);
 315   if (s.endswith(filename))
 316     return true;
 317   return !s.empty() && s.drop_back().endswith(filename);
 318 }
 319
 320 static bool isCrtbegin(StringRef s) { return isCrtBeginEnd(s, "crtbegin"); }
 321 static bool isCrtend(StringRef s) { return isCrtBeginEnd(s, "crtend"); }
 322
 323 // .ctors and .dtors are sorted by this priority from highest to lowest.
 324 //
 325 //  1. The section was contained in crtbegin (crtbegin contains
 326 //     some sentinel value in its .ctors and .dtors so that the runtime
 327 //     can find the beginning of the sections.)
 328 //
 329 //  2. The section has an optional priority value in the form of ".ctors.N"
 330 //     or ".dtors.N" where N is a number. Unlike .{init,fini}_array,
 331 //     they are compared as string rather than number.
 332 //
 333 //  3. The section is just ".ctors" or ".dtors".
 334 //
 335 //  4. The section was contained in crtend, which contains an end marker.
 336 //
 337 // In an ideal world, we don't need this function because .init_array and
 338 // .ctors are duplicate features (and .init_array is newer.) However, there
 339 // are too many real-world use cases of .ctors, so we had no choice to
 340 // support that with this rather ad-hoc semantics.
 341 static bool compCtors(const InputSection *a, const InputSection *b) {
 342   bool beginA = isCrtbegin(a->file->getName());
 343   bool beginB = isCrtbegin(b->file->getName());
 344   if (beginA != beginB)
 345     return beginA;
 346   bool endA = isCrtend(a->file->getName());
 347   bool endB = isCrtend(b->file->getName());
 348   if (endA != endB)
 349     return endB;
 350   StringRef x = a->name;
 351   StringRef y = b->name;
 352   assert(x.startswith(".ctors") || x.startswith(".dtors"));
 353   assert(y.startswith(".ctors") || y.startswith(".dtors"));
 354   x = x.substr(6);
 355   y = y.substr(6);
 356   return x < y;
 357 }
 358
 359 // Sorts input sections by the special rules for .ctors and .dtors.
 360 // Unfortunately, the rules are different from the one for .{init,fini}_array.
 361 // Read the comment above.
 362 void OutputSection::sortCtorsDtors() {
 363   assert(sectionCommands.size() == 1);
 364   auto *isd = cast<InputSectionDescription>(sectionCommands[0]);
 365   llvm::stable_sort(isd->sections, compCtors);
 366 }
 367
 368 // If an input string is in the form of "foo.N" where N is a number,
 369 // return N. Otherwise, returns 65536, which is one greater than the
 370 // lowest priority.
 371 int elf::getPriority(StringRef s) {
 372   size_t pos = s.rfind('.');
 373   if (pos == StringRef::npos)
 374     return 65536;
 375   int v;
 376   if (!to_integer(s.substr(pos + 1), v, 10))
 377     return 65536;
 378   return v;
 379 }
 380
 381 std::vector<InputSection *> elf::getInputSections(OutputSection *os) {
 382   std::vector<InputSection *> ret;
 383   for (BaseCommand *base : os->sectionCommands)
 384     if (auto *isd = dyn_cast<InputSectionDescription>(base))
 385       ret.insert(ret.end(), isd->sections.begin(), isd->sections.end());
 386   return ret;
 387 }
 388
 389 // Sorts input sections by section name suffixes, so that .foo.N comes
 390 // before .foo.M if N < M. Used to sort .{init,fini}_array.N sections.
 391 // We want to keep the original order if the priorities are the same
 392 // because the compiler keeps the original initialization order in a
 393 // translation unit and we need to respect that.
 394 // For more detail, read the section of the GCC's manual about init_priority.
 395 void OutputSection::sortInitFini() {
 396   // Sort sections by priority.
 397   sort([](InputSectionBase *s) { return getPriority(s->name); });
 398 }
 399
 400 std::array<uint8_t, 4> OutputSection::getFiller() {
 401   if (filler)
 402     return *filler;
 403   if (flags & SHF_EXECINSTR)
 404     return target->trapInstr;
 405   return {0, 0, 0, 0};
 406 }
 407
 408 template void OutputSection::writeHeaderTo<ELF32LE>(ELF32LE::Shdr *Shdr);
 409 template void OutputSection::writeHeaderTo<ELF32BE>(ELF32BE::Shdr *Shdr);
 410 template void OutputSection::writeHeaderTo<ELF64LE>(ELF64LE::Shdr *Shdr);
 411 template void OutputSection::writeHeaderTo<ELF64BE>(ELF64BE::Shdr *Shdr);
 412
 413 template void OutputSection::writeTo<ELF32LE>(uint8_t *Buf);
 414 template void OutputSection::writeTo<ELF32BE>(uint8_t *Buf);
 415 template void OutputSection::writeTo<ELF64LE>(uint8_t *Buf);
 416 template void OutputSection::writeTo<ELF64BE>(uint8_t *Buf);
 417
 418 template void OutputSection::maybeCompress<ELF32LE>();
 419 template void OutputSection::maybeCompress<ELF32BE>();
 420 template void OutputSection::maybeCompress<ELF64LE>();
 421 template void OutputSection::maybeCompress<ELF64BE>();