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