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

   1 //===- LinkerScript.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 // This file contains the parser/evaluator of the linker script.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "LinkerScript.h"
  14 #include "Config.h"
  15 #include "InputSection.h"
  16 #include "OutputSections.h"
  17 #include "SymbolTable.h"
  18 #include "Symbols.h"
  19 #include "SyntheticSections.h"
  20 #include "Target.h"
  21 #include "Writer.h"
  22 #include "lld/Common/Memory.h"
  23 #include "lld/Common/Strings.h"
  24 #include "lld/Common/Threads.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/ADT/StringRef.h"
  27 #include "llvm/BinaryFormat/ELF.h"
  28 #include "llvm/Support/Casting.h"
  29 #include "llvm/Support/Endian.h"
  30 #include "llvm/Support/ErrorHandling.h"
  31 #include "llvm/Support/FileSystem.h"
  32 #include "llvm/Support/Path.h"
  33 #include <algorithm>
  34 #include <cassert>
  35 #include <cstddef>
  36 #include <cstdint>
  37 #include <iterator>
  38 #include <limits>
  39 #include <string>
  40 #include <vector>
  41
  42 using namespace llvm;
  43 using namespace llvm::ELF;
  44 using namespace llvm::object;
  45 using namespace llvm::support::endian;
  46 using namespace lld;
  47 using namespace lld::elf;
  48
  49 LinkerScript *elf::script;
  50
  51 static uint64_t getOutputSectionVA(SectionBase *inputSec, StringRef loc) {
  52   if (OutputSection *os = inputSec->getOutputSection())
  53     return os->addr;
  54   error(loc + ": unable to evaluate expression: input section " +
  55         inputSec->name + " has no output section assigned");
  56   return 0;
  57 }
  58
  59 uint64_t ExprValue::getValue() const {
  60   if (sec)
  61     return alignTo(sec->getOffset(val) + getOutputSectionVA(sec, loc),
  62                    alignment);
  63   return alignTo(val, alignment);
  64 }
  65
  66 uint64_t ExprValue::getSecAddr() const {
  67   if (sec)
  68     return sec->getOffset(0) + getOutputSectionVA(sec, loc);
  69   return 0;
  70 }
  71
  72 uint64_t ExprValue::getSectionOffset() const {
  73   // If the alignment is trivial, we don't have to compute the full
  74   // value to know the offset. This allows this function to succeed in
  75   // cases where the output section is not yet known.
  76   if (alignment == 1 && (!sec || !sec->getOutputSection()))
  77     return val;
  78   return getValue() - getSecAddr();
  79 }
  80
  81 OutputSection *LinkerScript::createOutputSection(StringRef name,
  82                                                  StringRef location) {
  83   OutputSection *&secRef = nameToOutputSection[name];
  84   OutputSection *sec;
  85   if (secRef && secRef->location.empty()) {
  86     // There was a forward reference.
  87     sec = secRef;
  88   } else {
  89     sec = make<OutputSection>(name, SHT_PROGBITS, 0);
  90     if (!secRef)
  91       secRef = sec;
  92   }
  93   sec->location = location;
  94   return sec;
  95 }
  96
  97 OutputSection *LinkerScript::getOrCreateOutputSection(StringRef name) {
  98   OutputSection *&cmdRef = nameToOutputSection[name];
  99   if (!cmdRef)
 100     cmdRef = make<OutputSection>(name, SHT_PROGBITS, 0);
 101   return cmdRef;
 102 }
 103
 104 // Expands the memory region by the specified size.
 105 static void expandMemoryRegion(MemoryRegion *memRegion, uint64_t size,
 106                                StringRef regionName, StringRef secName) {
 107   memRegion->curPos += size;
 108   uint64_t newSize = memRegion->curPos - memRegion->origin;
 109   if (newSize > memRegion->length)
 110     error("section '" + secName + "' will not fit in region '" + regionName +
 111           "': overflowed by " + Twine(newSize - memRegion->length) + " bytes");
 112 }
 113
 114 void LinkerScript::expandMemoryRegions(uint64_t size) {
 115   if (ctx->memRegion)
 116     expandMemoryRegion(ctx->memRegion, size, ctx->memRegion->name,
 117                        ctx->outSec->name);
 118   // Only expand the LMARegion if it is different from memRegion.
 119   if (ctx->lmaRegion && ctx->memRegion != ctx->lmaRegion)
 120     expandMemoryRegion(ctx->lmaRegion, size, ctx->lmaRegion->name,
 121                        ctx->outSec->name);
 122 }
 123
 124 void LinkerScript::expandOutputSection(uint64_t size) {
 125   ctx->outSec->size += size;
 126   expandMemoryRegions(size);
 127 }
 128
 129 void LinkerScript::setDot(Expr e, const Twine &loc, bool inSec) {
 130   uint64_t val = e().getValue();
 131   if (val < dot && inSec)
 132     error(loc + ": unable to move location counter backward for: " +
 133           ctx->outSec->name);
 134
 135   // Update to location counter means update to section size.
 136   if (inSec)
 137     expandOutputSection(val - dot);
 138
 139   dot = val;
 140 }
 141
 142 // Used for handling linker symbol assignments, for both finalizing
 143 // their values and doing early declarations. Returns true if symbol
 144 // should be defined from linker script.
 145 static bool shouldDefineSym(SymbolAssignment *cmd) {
 146   if (cmd->name == ".")
 147     return false;
 148
 149   if (!cmd->provide)
 150     return true;
 151
 152   // If a symbol was in PROVIDE(), we need to define it only
 153   // when it is a referenced undefined symbol.
 154   Symbol *b = symtab->find(cmd->name);
 155   if (b && !b->isDefined())
 156     return true;
 157   return false;
 158 }
 159
 160 // This function is called from processSectionCommands,
 161 // while we are fixing the output section layout.
 162 void LinkerScript::addSymbol(SymbolAssignment *cmd) {
 163   if (!shouldDefineSym(cmd))
 164     return;
 165
 166   // Define a symbol.
 167   ExprValue value = cmd->expression();
 168   SectionBase *sec = value.isAbsolute() ? nullptr : value.sec;
 169   uint8_t visibility = cmd->hidden ? STV_HIDDEN : STV_DEFAULT;
 170
 171   // When this function is called, section addresses have not been
 172   // fixed yet. So, we may or may not know the value of the RHS
 173   // expression.
 174   //
 175   // For example, if an expression is `x = 42`, we know x is always 42.
 176   // However, if an expression is `x = .`, there's no way to know its
 177   // value at the moment.
 178   //
 179   // We want to set symbol values early if we can. This allows us to
 180   // use symbols as variables in linker scripts. Doing so allows us to
 181   // write expressions like this: `alignment = 16; . = ALIGN(., alignment)`.
 182   uint64_t symValue = value.sec ? 0 : value.getValue();
 183
 184   Defined New(nullptr, cmd->name, STB_GLOBAL, visibility, STT_NOTYPE, symValue,
 185               0, sec);
 186
 187   Symbol *sym = symtab->insert(cmd->name);
 188   sym->mergeProperties(New);
 189   sym->replace(New);
 190   cmd->sym = cast<Defined>(sym);
 191 }
 192
 193 // This function is called from LinkerScript::declareSymbols.
 194 // It creates a placeholder symbol if needed.
 195 static void declareSymbol(SymbolAssignment *cmd) {
 196   if (!shouldDefineSym(cmd))
 197     return;
 198
 199   uint8_t visibility = cmd->hidden ? STV_HIDDEN : STV_DEFAULT;
 200   Defined New(nullptr, cmd->name, STB_GLOBAL, visibility, STT_NOTYPE, 0, 0,
 201               nullptr);
 202
 203   // We can't calculate final value right now.
 204   Symbol *sym = symtab->insert(cmd->name);
 205   sym->mergeProperties(New);
 206   sym->replace(New);
 207
 208   cmd->sym = cast<Defined>(sym);
 209   cmd->provide = false;
 210   sym->scriptDefined = true;
 211 }
 212
 213 // This method is used to handle INSERT AFTER statement. Here we rebuild
 214 // the list of script commands to mix sections inserted into.
 215 void LinkerScript::processInsertCommands() {
 216   std::vector<BaseCommand *> v;
 217   auto insert = [&](std::vector<BaseCommand *> &from) {
 218     v.insert(v.end(), from.begin(), from.end());
 219     from.clear();
 220   };
 221
 222   for (BaseCommand *base : sectionCommands) {
 223     if (auto *os = dyn_cast<OutputSection>(base)) {
 224       insert(insertBeforeCommands[os->name]);
 225       v.push_back(base);
 226       insert(insertAfterCommands[os->name]);
 227       continue;
 228     }
 229     v.push_back(base);
 230   }
 231
 232   for (auto &cmds : {insertBeforeCommands, insertAfterCommands})
 233     for (const std::pair<StringRef, std::vector<BaseCommand *>> &p : cmds)
 234       if (!p.second.empty())
 235         error("unable to INSERT AFTER/BEFORE " + p.first +
 236               ": section not defined");
 237
 238   sectionCommands = std::move(v);
 239 }
 240
 241 // Symbols defined in script should not be inlined by LTO. At the same time
 242 // we don't know their final values until late stages of link. Here we scan
 243 // over symbol assignment commands and create placeholder symbols if needed.
 244 void LinkerScript::declareSymbols() {
 245   assert(!ctx);
 246   for (BaseCommand *base : sectionCommands) {
 247     if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
 248       declareSymbol(cmd);
 249       continue;
 250     }
 251
 252     // If the output section directive has constraints,
 253     // we can't say for sure if it is going to be included or not.
 254     // Skip such sections for now. Improve the checks if we ever
 255     // need symbols from that sections to be declared early.
 256     auto *sec = cast<OutputSection>(base);
 257     if (sec->constraint != ConstraintKind::NoConstraint)
 258       continue;
 259     for (BaseCommand *base2 : sec->sectionCommands)
 260       if (auto *cmd = dyn_cast<SymbolAssignment>(base2))
 261         declareSymbol(cmd);
 262   }
 263 }
 264
 265 // This function is called from assignAddresses, while we are
 266 // fixing the output section addresses. This function is supposed
 267 // to set the final value for a given symbol assignment.
 268 void LinkerScript::assignSymbol(SymbolAssignment *cmd, bool inSec) {
 269   if (cmd->name == ".") {
 270     setDot(cmd->expression, cmd->location, inSec);
 271     return;
 272   }
 273
 274   if (!cmd->sym)
 275     return;
 276
 277   ExprValue v = cmd->expression();
 278   if (v.isAbsolute()) {
 279     cmd->sym->section = nullptr;
 280     cmd->sym->value = v.getValue();
 281   } else {
 282     cmd->sym->section = v.sec;
 283     cmd->sym->value = v.getSectionOffset();
 284   }
 285 }
 286
 287 static std::string getFilename(InputFile *file) {
 288   if (!file)
 289     return "";
 290   if (file->archiveName.empty())
 291     return file->getName();
 292   return (file->archiveName + "(" + file->getName() + ")").str();
 293 }
 294
 295 bool LinkerScript::shouldKeep(InputSectionBase *s) {
 296   if (keptSections.empty())
 297     return false;
 298   std::string filename = getFilename(s->file);
 299   for (InputSectionDescription *id : keptSections)
 300     if (id->filePat.match(filename))
 301       for (SectionPattern &p : id->sectionPatterns)
 302         if (p.sectionPat.match(s->name))
 303           return true;
 304   return false;
 305 }
 306
 307 // A helper function for the SORT() command.
 308 static std::function<bool(InputSectionBase *, InputSectionBase *)>
 309 getComparator(SortSectionPolicy k) {
 310   switch (k) {
 311   case SortSectionPolicy::Alignment:
 312     return [](InputSectionBase *a, InputSectionBase *b) {
 313       // ">" is not a mistake. Sections with larger alignments are placed
 314       // before sections with smaller alignments in order to reduce the
 315       // amount of padding necessary. This is compatible with GNU.
 316       return a->alignment > b->alignment;
 317     };
 318   case SortSectionPolicy::Name:
 319     return [](InputSectionBase *a, InputSectionBase *b) {
 320       return a->name < b->name;
 321     };
 322   case SortSectionPolicy::Priority:
 323     return [](InputSectionBase *a, InputSectionBase *b) {
 324       return getPriority(a->name) < getPriority(b->name);
 325     };
 326   default:
 327     llvm_unreachable("unknown sort policy");
 328   }
 329 }
 330
 331 // A helper function for the SORT() command.
 332 static bool matchConstraints(ArrayRef<InputSection *> sections,
 333                              ConstraintKind kind) {
 334   if (kind == ConstraintKind::NoConstraint)
 335     return true;
 336
 337   bool isRW = llvm::any_of(
 338       sections, [](InputSection *sec) { return sec->flags & SHF_WRITE; });
 339
 340   return (isRW && kind == ConstraintKind::ReadWrite) ||
 341          (!isRW && kind == ConstraintKind::ReadOnly);
 342 }
 343
 344 static void sortSections(MutableArrayRef<InputSection *> vec,
 345                          SortSectionPolicy k) {
 346   if (k != SortSectionPolicy::Default && k != SortSectionPolicy::None)
 347     llvm::stable_sort(vec, getComparator(k));
 348 }
 349
 350 // Sort sections as instructed by SORT-family commands and --sort-section
 351 // option. Because SORT-family commands can be nested at most two depth
 352 // (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
 353 // line option is respected even if a SORT command is given, the exact
 354 // behavior we have here is a bit complicated. Here are the rules.
 355 //
 356 // 1. If two SORT commands are given, --sort-section is ignored.
 357 // 2. If one SORT command is given, and if it is not SORT_NONE,
 358 //    --sort-section is handled as an inner SORT command.
 359 // 3. If one SORT command is given, and if it is SORT_NONE, don't sort.
 360 // 4. If no SORT command is given, sort according to --sort-section.
 361 static void sortInputSections(MutableArrayRef<InputSection *> vec,
 362                               const SectionPattern &pat) {
 363   if (pat.sortOuter == SortSectionPolicy::None)
 364     return;
 365
 366   if (pat.sortInner == SortSectionPolicy::Default)
 367     sortSections(vec, config->sortSection);
 368   else
 369     sortSections(vec, pat.sortInner);
 370   sortSections(vec, pat.sortOuter);
 371 }
 372
 373 // Compute and remember which sections the InputSectionDescription matches.
 374 std::vector<InputSection *>
 375 LinkerScript::computeInputSections(const InputSectionDescription *cmd) {
 376   std::vector<InputSection *> ret;
 377
 378   // Collects all sections that satisfy constraints of Cmd.
 379   for (const SectionPattern &pat : cmd->sectionPatterns) {
 380     size_t sizeBefore = ret.size();
 381
 382     for (InputSectionBase *sec : inputSections) {
 383       if (!sec->isLive() || sec->assigned)
 384         continue;
 385
 386       // For -emit-relocs we have to ignore entries like
 387       //   .rela.dyn : { *(.rela.data) }
 388       // which are common because they are in the default bfd script.
 389       // We do not ignore SHT_REL[A] linker-synthesized sections here because
 390       // want to support scripts that do custom layout for them.
 391       if (auto *isec = dyn_cast<InputSection>(sec))
 392         if (isec->getRelocatedSection())
 393           continue;
 394
 395       std::string filename = getFilename(sec->file);
 396       if (!cmd->filePat.match(filename) ||
 397           pat.excludedFilePat.match(filename) ||
 398           !pat.sectionPat.match(sec->name))
 399         continue;
 400
 401       // It is safe to assume that Sec is an InputSection
 402       // because mergeable or EH input sections have already been
 403       // handled and eliminated.
 404       ret.push_back(cast<InputSection>(sec));
 405       sec->assigned = true;
 406     }
 407
 408     sortInputSections(MutableArrayRef<InputSection *>(ret).slice(sizeBefore),
 409                       pat);
 410   }
 411   return ret;
 412 }
 413
 414 void LinkerScript::discard(ArrayRef<InputSection *> v) {
 415   for (InputSection *s : v) {
 416     if (s == in.shStrTab || s == mainPart->relaDyn || s == mainPart->relrDyn)
 417       error("discarding " + s->name + " section is not allowed");
 418
 419     // You can discard .hash and .gnu.hash sections by linker scripts. Since
 420     // they are synthesized sections, we need to handle them differently than
 421     // other regular sections.
 422     if (s == mainPart->gnuHashTab)
 423       mainPart->gnuHashTab = nullptr;
 424     if (s == mainPart->hashTab)
 425       mainPart->hashTab = nullptr;
 426
 427     s->assigned = false;
 428     s->markDead();
 429     discard(s->dependentSections);
 430   }
 431 }
 432
 433 std::vector<InputSection *>
 434 LinkerScript::createInputSectionList(OutputSection &outCmd) {
 435   std::vector<InputSection *> ret;
 436
 437   for (BaseCommand *base : outCmd.sectionCommands) {
 438     if (auto *cmd = dyn_cast<InputSectionDescription>(base)) {
 439       cmd->sections = computeInputSections(cmd);
 440       ret.insert(ret.end(), cmd->sections.begin(), cmd->sections.end());
 441     }
 442   }
 443   return ret;
 444 }
 445
 446 void LinkerScript::processSectionCommands() {
 447   // A symbol can be assigned before any section is mentioned in the linker
 448   // script. In an DSO, the symbol values are addresses, so the only important
 449   // section values are:
 450   // * SHN_UNDEF
 451   // * SHN_ABS
 452   // * Any value meaning a regular section.
 453   // To handle that, create a dummy aether section that fills the void before
 454   // the linker scripts switches to another section. It has an index of one
 455   // which will map to whatever the first actual section is.
 456   aether = make<OutputSection>("", 0, SHF_ALLOC);
 457   aether->sectionIndex = 1;
 458
 459   // Ctx captures the local AddressState and makes it accessible deliberately.
 460   // This is needed as there are some cases where we cannot just
 461   // thread the current state through to a lambda function created by the
 462   // script parser.
 463   auto deleter = make_unique<AddressState>();
 464   ctx = deleter.get();
 465   ctx->outSec = aether;
 466
 467   size_t i = 0;
 468   // Add input sections to output sections.
 469   for (BaseCommand *base : sectionCommands) {
 470     // Handle symbol assignments outside of any output section.
 471     if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
 472       addSymbol(cmd);
 473       continue;
 474     }
 475
 476     if (auto *sec = dyn_cast<OutputSection>(base)) {
 477       std::vector<InputSection *> v = createInputSectionList(*sec);
 478
 479       // The output section name `/DISCARD/' is special.
 480       // Any input section assigned to it is discarded.
 481       if (sec->name == "/DISCARD/") {
 482         discard(v);
 483         sec->sectionCommands.clear();
 484         continue;
 485       }
 486
 487       // This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive
 488       // ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input
 489       // sections satisfy a given constraint. If not, a directive is handled
 490       // as if it wasn't present from the beginning.
 491       //
 492       // Because we'll iterate over SectionCommands many more times, the easy
 493       // way to "make it as if it wasn't present" is to make it empty.
 494       if (!matchConstraints(v, sec->constraint)) {
 495         for (InputSectionBase *s : v)
 496           s->assigned = false;
 497         sec->sectionCommands.clear();
 498         continue;
 499       }
 500
 501       // A directive may contain symbol definitions like this:
 502       // ".foo : { ...; bar = .; }". Handle them.
 503       for (BaseCommand *base : sec->sectionCommands)
 504         if (auto *outCmd = dyn_cast<SymbolAssignment>(base))
 505           addSymbol(outCmd);
 506
 507       // Handle subalign (e.g. ".foo : SUBALIGN(32) { ... }"). If subalign
 508       // is given, input sections are aligned to that value, whether the
 509       // given value is larger or smaller than the original section alignment.
 510       if (sec->subalignExpr) {
 511         uint32_t subalign = sec->subalignExpr().getValue();
 512         for (InputSectionBase *s : v)
 513           s->alignment = subalign;
 514       }
 515
 516       // Add input sections to an output section.
 517       for (InputSection *s : v)
 518         sec->addSection(s);
 519
 520       sec->sectionIndex = i++;
 521       if (sec->noload)
 522         sec->type = SHT_NOBITS;
 523       if (sec->nonAlloc)
 524         sec->flags &= ~(uint64_t)SHF_ALLOC;
 525     }
 526   }
 527   ctx = nullptr;
 528 }
 529
 530 static OutputSection *findByName(ArrayRef<BaseCommand *> vec,
 531                                  StringRef name) {
 532   for (BaseCommand *base : vec)
 533     if (auto *sec = dyn_cast<OutputSection>(base))
 534       if (sec->name == name)
 535         return sec;
 536   return nullptr;
 537 }
 538
 539 static OutputSection *createSection(InputSectionBase *isec,
 540                                     StringRef outsecName) {
 541   OutputSection *sec = script->createOutputSection(outsecName, "<internal>");
 542   sec->addSection(cast<InputSection>(isec));
 543   return sec;
 544 }
 545
 546 static OutputSection *
 547 addInputSec(StringMap<TinyPtrVector<OutputSection *>> &map,
 548             InputSectionBase *isec, StringRef outsecName) {
 549   // Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r
 550   // option is given. A section with SHT_GROUP defines a "section group", and
 551   // its members have SHF_GROUP attribute. Usually these flags have already been
 552   // stripped by InputFiles.cpp as section groups are processed and uniquified.
 553   // However, for the -r option, we want to pass through all section groups
 554   // as-is because adding/removing members or merging them with other groups
 555   // change their semantics.
 556   if (isec->type == SHT_GROUP || (isec->flags & SHF_GROUP))
 557     return createSection(isec, outsecName);
 558
 559   // Imagine .zed : { *(.foo) *(.bar) } script. Both foo and bar may have
 560   // relocation sections .rela.foo and .rela.bar for example. Most tools do
 561   // not allow multiple REL[A] sections for output section. Hence we
 562   // should combine these relocation sections into single output.
 563   // We skip synthetic sections because it can be .rela.dyn/.rela.plt or any
 564   // other REL[A] sections created by linker itself.
 565   if (!isa<SyntheticSection>(isec) &&
 566       (isec->type == SHT_REL || isec->type == SHT_RELA)) {
 567     auto *sec = cast<InputSection>(isec);
 568     OutputSection *out = sec->getRelocatedSection()->getOutputSection();
 569
 570     if (out->relocationSection) {
 571       out->relocationSection->addSection(sec);
 572       return nullptr;
 573     }
 574
 575     out->relocationSection = createSection(isec, outsecName);
 576     return out->relocationSection;
 577   }
 578
 579   // When control reaches here, mergeable sections have already been merged into
 580   // synthetic sections. For relocatable case we want to create one output
 581   // section per syntetic section so that they have a valid sh_entsize.
 582   if (config->relocatable && (isec->flags & SHF_MERGE))
 583     return createSection(isec, outsecName);
 584
 585   //  The ELF spec just says
 586   // ----------------------------------------------------------------
 587   // In the first phase, input sections that match in name, type and
 588   // attribute flags should be concatenated into single sections.
 589   // ----------------------------------------------------------------
 590   //
 591   // However, it is clear that at least some flags have to be ignored for
 592   // section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be
 593   // ignored. We should not have two output .text sections just because one was
 594   // in a group and another was not for example.
 595   //
 596   // It also seems that wording was a late addition and didn't get the
 597   // necessary scrutiny.
 598   //
 599   // Merging sections with different flags is expected by some users. One
 600   // reason is that if one file has
 601   //
 602   // int *const bar __attribute__((section(".foo"))) = (int *)0;
 603   //
 604   // gcc with -fPIC will produce a read only .foo section. But if another
 605   // file has
 606   //
 607   // int zed;
 608   // int *const bar __attribute__((section(".foo"))) = (int *)&zed;
 609   //
 610   // gcc with -fPIC will produce a read write section.
 611   //
 612   // Last but not least, when using linker script the merge rules are forced by
 613   // the script. Unfortunately, linker scripts are name based. This means that
 614   // expressions like *(.foo*) can refer to multiple input sections with
 615   // different flags. We cannot put them in different output sections or we
 616   // would produce wrong results for
 617   //
 618   // start = .; *(.foo.*) end = .; *(.bar)
 619   //
 620   // and a mapping of .foo1 and .bar1 to one section and .foo2 and .bar2 to
 621   // another. The problem is that there is no way to layout those output
 622   // sections such that the .foo sections are the only thing between the start
 623   // and end symbols.
 624   //
 625   // Given the above issues, we instead merge sections by name and error on
 626   // incompatible types and flags.
 627   TinyPtrVector<OutputSection *> &v = map[outsecName];
 628   for (OutputSection *sec : v) {
 629     if (sec->partition != isec->partition)
 630       continue;
 631     sec->addSection(cast<InputSection>(isec));
 632     return nullptr;
 633   }
 634
 635   OutputSection *sec = createSection(isec, outsecName);
 636   v.push_back(sec);
 637   return sec;
 638 }
 639
 640 // Add sections that didn't match any sections command.
 641 void LinkerScript::addOrphanSections() {
 642   StringMap<TinyPtrVector<OutputSection *>> map;
 643   std::vector<OutputSection *> v;
 644
 645   auto add = [&](InputSectionBase *s) {
 646     if (!s->isLive() || s->parent)
 647       return;
 648
 649     StringRef name = getOutputSectionName(s);
 650
 651     if (config->orphanHandling == OrphanHandlingPolicy::Error)
 652       error(toString(s) + " is being placed in '" + name + "'");
 653     else if (config->orphanHandling == OrphanHandlingPolicy::Warn)
 654       warn(toString(s) + " is being placed in '" + name + "'");
 655
 656     if (OutputSection *sec = findByName(sectionCommands, name)) {
 657       sec->addSection(cast<InputSection>(s));
 658       return;
 659     }
 660
 661     if (OutputSection *os = addInputSec(map, s, name))
 662       v.push_back(os);
 663     assert(s->getOutputSection()->sectionIndex == UINT32_MAX);
 664   };
 665
 666   // For futher --emit-reloc handling code we need target output section
 667   // to be created before we create relocation output section, so we want
 668   // to create target sections first. We do not want priority handling
 669   // for synthetic sections because them are special.
 670   for (InputSectionBase *isec : inputSections) {
 671     if (auto *sec = dyn_cast<InputSection>(isec))
 672       if (InputSectionBase *rel = sec->getRelocatedSection())
 673         if (auto *relIS = dyn_cast_or_null<InputSectionBase>(rel->parent))
 674           add(relIS);
 675     add(isec);
 676   }
 677
 678   // If no SECTIONS command was given, we should insert sections commands
 679   // before others, so that we can handle scripts which refers them,
 680   // for example: "foo = ABSOLUTE(ADDR(.text)));".
 681   // When SECTIONS command is present we just add all orphans to the end.
 682   if (hasSectionsCommand)
 683     sectionCommands.insert(sectionCommands.end(), v.begin(), v.end());
 684   else
 685     sectionCommands.insert(sectionCommands.begin(), v.begin(), v.end());
 686 }
 687
 688 uint64_t LinkerScript::advance(uint64_t size, unsigned alignment) {
 689   bool isTbss =
 690       (ctx->outSec->flags & SHF_TLS) && ctx->outSec->type == SHT_NOBITS;
 691   uint64_t start = isTbss ? dot + ctx->threadBssOffset : dot;
 692   start = alignTo(start, alignment);
 693   uint64_t end = start + size;
 694
 695   if (isTbss)
 696     ctx->threadBssOffset = end - dot;
 697   else
 698     dot = end;
 699   return end;
 700 }
 701
 702 void LinkerScript::output(InputSection *s) {
 703   assert(ctx->outSec == s->getParent());
 704   uint64_t before = advance(0, 1);
 705   uint64_t pos = advance(s->getSize(), s->alignment);
 706   s->outSecOff = pos - s->getSize() - ctx->outSec->addr;
 707
 708   // Update output section size after adding each section. This is so that
 709   // SIZEOF works correctly in the case below:
 710   // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
 711   expandOutputSection(pos - before);
 712 }
 713
 714 void LinkerScript::switchTo(OutputSection *sec) {
 715   ctx->outSec = sec;
 716
 717   uint64_t before = advance(0, 1);
 718   ctx->outSec->addr = advance(0, ctx->outSec->alignment);
 719   expandMemoryRegions(ctx->outSec->addr - before);
 720 }
 721
 722 // This function searches for a memory region to place the given output
 723 // section in. If found, a pointer to the appropriate memory region is
 724 // returned. Otherwise, a nullptr is returned.
 725 MemoryRegion *LinkerScript::findMemoryRegion(OutputSection *sec) {
 726   // If a memory region name was specified in the output section command,
 727   // then try to find that region first.
 728   if (!sec->memoryRegionName.empty()) {
 729     if (MemoryRegion *m = memoryRegions.lookup(sec->memoryRegionName))
 730       return m;
 731     error("memory region '" + sec->memoryRegionName + "' not declared");
 732     return nullptr;
 733   }
 734
 735   // If at least one memory region is defined, all sections must
 736   // belong to some memory region. Otherwise, we don't need to do
 737   // anything for memory regions.
 738   if (memoryRegions.empty())
 739     return nullptr;
 740
 741   // See if a region can be found by matching section flags.
 742   for (auto &pair : memoryRegions) {
 743     MemoryRegion *m = pair.second;
 744     if ((m->flags & sec->flags) && (m->negFlags & sec->flags) == 0)
 745       return m;
 746   }
 747
 748   // Otherwise, no suitable region was found.
 749   if (sec->flags & SHF_ALLOC)
 750     error("no memory region specified for section '" + sec->name + "'");
 751   return nullptr;
 752 }
 753
 754 static OutputSection *findFirstSection(PhdrEntry *load) {
 755   for (OutputSection *sec : outputSections)
 756     if (sec->ptLoad == load)
 757       return sec;
 758   return nullptr;
 759 }
 760
 761 // This function assigns offsets to input sections and an output section
 762 // for a single sections command (e.g. ".text { *(.text); }").
 763 void LinkerScript::assignOffsets(OutputSection *sec) {
 764   if (!(sec->flags & SHF_ALLOC))
 765     dot = 0;
 766
 767   ctx->memRegion = sec->memRegion;
 768   ctx->lmaRegion = sec->lmaRegion;
 769   if (ctx->memRegion)
 770     dot = ctx->memRegion->curPos;
 771
 772   if ((sec->flags & SHF_ALLOC) && sec->addrExpr)
 773     setDot(sec->addrExpr, sec->location, false);
 774
 775   switchTo(sec);
 776
 777   if (sec->lmaExpr)
 778     ctx->lmaOffset = sec->lmaExpr().getValue() - dot;
 779
 780   if (MemoryRegion *mr = sec->lmaRegion)
 781     ctx->lmaOffset = mr->curPos - dot;
 782
 783   // If neither AT nor AT> is specified for an allocatable section, the linker
 784   // will set the LMA such that the difference between VMA and LMA for the
 785   // section is the same as the preceding output section in the same region
 786   // https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html
 787   // This, however, should only be done by the first "non-header" section
 788   // in the segment.
 789   if (PhdrEntry *l = ctx->outSec->ptLoad)
 790     if (sec == findFirstSection(l))
 791       l->lmaOffset = ctx->lmaOffset;
 792
 793   // We can call this method multiple times during the creation of
 794   // thunks and want to start over calculation each time.
 795   sec->size = 0;
 796
 797   // We visited SectionsCommands from processSectionCommands to
 798   // layout sections. Now, we visit SectionsCommands again to fix
 799   // section offsets.
 800   for (BaseCommand *base : sec->sectionCommands) {
 801     // This handles the assignments to symbol or to the dot.
 802     if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
 803       cmd->addr = dot;
 804       assignSymbol(cmd, true);
 805       cmd->size = dot - cmd->addr;
 806       continue;
 807     }
 808
 809     // Handle BYTE(), SHORT(), LONG(), or QUAD().
 810     if (auto *cmd = dyn_cast<ByteCommand>(base)) {
 811       cmd->offset = dot - ctx->outSec->addr;
 812       dot += cmd->size;
 813       expandOutputSection(cmd->size);
 814       continue;
 815     }
 816
 817     // Handle a single input section description command.
 818     // It calculates and assigns the offsets for each section and also
 819     // updates the output section size.
 820     for (InputSection *sec : cast<InputSectionDescription>(base)->sections)
 821       output(sec);
 822   }
 823 }
 824
 825 static bool isDiscardable(OutputSection &sec) {
 826   if (sec.name == "/DISCARD/")
 827     return true;
 828
 829   // We do not remove empty sections that are explicitly
 830   // assigned to any segment.
 831   if (!sec.phdrs.empty())
 832     return false;
 833
 834   // We do not want to remove OutputSections with expressions that reference
 835   // symbols even if the OutputSection is empty. We want to ensure that the
 836   // expressions can be evaluated and report an error if they cannot.
 837   if (sec.expressionsUseSymbols)
 838     return false;
 839
 840   // OutputSections may be referenced by name in ADDR and LOADADDR expressions,
 841   // as an empty Section can has a valid VMA and LMA we keep the OutputSection
 842   // to maintain the integrity of the other Expression.
 843   if (sec.usedInExpression)
 844     return false;
 845
 846   for (BaseCommand *base : sec.sectionCommands) {
 847     if (auto cmd = dyn_cast<SymbolAssignment>(base))
 848       // Don't create empty output sections just for unreferenced PROVIDE
 849       // symbols.
 850       if (cmd->name != "." && !cmd->sym)
 851         continue;
 852
 853     if (!isa<InputSectionDescription>(*base))
 854       return false;
 855   }
 856   return true;
 857 }
 858
 859 void LinkerScript::adjustSectionsBeforeSorting() {
 860   // If the output section contains only symbol assignments, create a
 861   // corresponding output section. The issue is what to do with linker script
 862   // like ".foo : { symbol = 42; }". One option would be to convert it to
 863   // "symbol = 42;". That is, move the symbol out of the empty section
 864   // description. That seems to be what bfd does for this simple case. The
 865   // problem is that this is not completely general. bfd will give up and
 866   // create a dummy section too if there is a ". = . + 1" inside the section
 867   // for example.
 868   // Given that we want to create the section, we have to worry what impact
 869   // it will have on the link. For example, if we just create a section with
 870   // 0 for flags, it would change which PT_LOADs are created.
 871   // We could remember that particular section is dummy and ignore it in
 872   // other parts of the linker, but unfortunately there are quite a few places
 873   // that would need to change:
 874   //   * The program header creation.
 875   //   * The orphan section placement.
 876   //   * The address assignment.
 877   // The other option is to pick flags that minimize the impact the section
 878   // will have on the rest of the linker. That is why we copy the flags from
 879   // the previous sections. Only a few flags are needed to keep the impact low.
 880   uint64_t flags = SHF_ALLOC;
 881
 882   for (BaseCommand *&cmd : sectionCommands) {
 883     auto *sec = dyn_cast<OutputSection>(cmd);
 884     if (!sec)
 885       continue;
 886
 887     // Handle align (e.g. ".foo : ALIGN(16) { ... }").
 888     if (sec->alignExpr)
 889       sec->alignment =
 890           std::max<uint32_t>(sec->alignment, sec->alignExpr().getValue());
 891
 892     // The input section might have been removed (if it was an empty synthetic
 893     // section), but we at least know the flags.
 894     if (sec->hasInputSections)
 895       flags = sec->flags;
 896
 897     // We do not want to keep any special flags for output section
 898     // in case it is empty.
 899     bool isEmpty = getInputSections(sec).empty();
 900     if (isEmpty)
 901       sec->flags = flags & ((sec->nonAlloc ? 0 : (uint64_t)SHF_ALLOC) |
 902                             SHF_WRITE | SHF_EXECINSTR);
 903
 904     if (isEmpty && isDiscardable(*sec)) {
 905       sec->markDead();
 906       cmd = nullptr;
 907     } else if (!sec->isLive()) {
 908       sec->markLive();
 909     }
 910   }
 911
 912   // It is common practice to use very generic linker scripts. So for any
 913   // given run some of the output sections in the script will be empty.
 914   // We could create corresponding empty output sections, but that would
 915   // clutter the output.
 916   // We instead remove trivially empty sections. The bfd linker seems even
 917   // more aggressive at removing them.
 918   llvm::erase_if(sectionCommands, [&](BaseCommand *base) { return !base; });
 919 }
 920
 921 void LinkerScript::adjustSectionsAfterSorting() {
 922   // Try and find an appropriate memory region to assign offsets in.
 923   for (BaseCommand *base : sectionCommands) {
 924     if (auto *sec = dyn_cast<OutputSection>(base)) {
 925       if (!sec->lmaRegionName.empty()) {
 926         if (MemoryRegion *m = memoryRegions.lookup(sec->lmaRegionName))
 927           sec->lmaRegion = m;
 928         else
 929           error("memory region '" + sec->lmaRegionName + "' not declared");
 930       }
 931       sec->memRegion = findMemoryRegion(sec);
 932     }
 933   }
 934
 935   // If output section command doesn't specify any segments,
 936   // and we haven't previously assigned any section to segment,
 937   // then we simply assign section to the very first load segment.
 938   // Below is an example of such linker script:
 939   // PHDRS { seg PT_LOAD; }
 940   // SECTIONS { .aaa : { *(.aaa) } }
 941   std::vector<StringRef> defPhdrs;
 942   auto firstPtLoad = llvm::find_if(phdrsCommands, [](const PhdrsCommand &cmd) {
 943     return cmd.type == PT_LOAD;
 944   });
 945   if (firstPtLoad != phdrsCommands.end())
 946     defPhdrs.push_back(firstPtLoad->name);
 947
 948   // Walk the commands and propagate the program headers to commands that don't
 949   // explicitly specify them.
 950   for (BaseCommand *base : sectionCommands) {
 951     auto *sec = dyn_cast<OutputSection>(base);
 952     if (!sec)
 953       continue;
 954
 955     if (sec->phdrs.empty()) {
 956       // To match the bfd linker script behaviour, only propagate program
 957       // headers to sections that are allocated.
 958       if (sec->flags & SHF_ALLOC)
 959         sec->phdrs = defPhdrs;
 960     } else {
 961       defPhdrs = sec->phdrs;
 962     }
 963   }
 964 }
 965
 966 static uint64_t computeBase(uint64_t min, bool allocateHeaders) {
 967   // If there is no SECTIONS or if the linkerscript is explicit about program
 968   // headers, do our best to allocate them.
 969   if (!script->hasSectionsCommand || allocateHeaders)
 970     return 0;
 971   // Otherwise only allocate program headers if that would not add a page.
 972   return alignDown(min, config->maxPageSize);
 973 }
 974
 975 // Try to find an address for the file and program headers output sections,
 976 // which were unconditionally added to the first PT_LOAD segment earlier.
 977 //
 978 // When using the default layout, we check if the headers fit below the first
 979 // allocated section. When using a linker script, we also check if the headers
 980 // are covered by the output section. This allows omitting the headers by not
 981 // leaving enough space for them in the linker script; this pattern is common
 982 // in embedded systems.
 983 //
 984 // If there isn't enough space for these sections, we'll remove them from the
 985 // PT_LOAD segment, and we'll also remove the PT_PHDR segment.
 986 void LinkerScript::allocateHeaders(std::vector<PhdrEntry *> &phdrs) {
 987   uint64_t min = std::numeric_limits<uint64_t>::max();
 988   for (OutputSection *sec : outputSections)
 989     if (sec->flags & SHF_ALLOC)
 990       min = std::min<uint64_t>(min, sec->addr);
 991
 992   auto it = llvm::find_if(
 993       phdrs, [](const PhdrEntry *e) { return e->p_type == PT_LOAD; });
 994   if (it == phdrs.end())
 995     return;
 996   PhdrEntry *firstPTLoad = *it;
 997
 998   bool hasExplicitHeaders =
 999       llvm::any_of(phdrsCommands, [](const PhdrsCommand &cmd) {
1000         return cmd.hasPhdrs || cmd.hasFilehdr;
1001       });
1002   bool paged = !config->omagic && !config->nmagic;
1003   uint64_t headerSize = getHeaderSize();
1004   if ((paged || hasExplicitHeaders) &&
1005       headerSize <= min - computeBase(min, hasExplicitHeaders)) {
1006     min = alignDown(min - headerSize, config->maxPageSize);
1007     Out::elfHeader->addr = min;
1008     Out::programHeaders->addr = min + Out::elfHeader->size;
1009     return;
1010   }
1011
1012   // Error if we were explicitly asked to allocate headers.
1013   if (hasExplicitHeaders)
1014     error("could not allocate headers");
1015
1016   Out::elfHeader->ptLoad = nullptr;
1017   Out::programHeaders->ptLoad = nullptr;
1018   firstPTLoad->firstSec = findFirstSection(firstPTLoad);
1019
1020   llvm::erase_if(phdrs,
1021                  [](const PhdrEntry *e) { return e->p_type == PT_PHDR; });
1022 }
1023
1024 LinkerScript::AddressState::AddressState() {
1025   for (auto &mri : script->memoryRegions) {
1026     MemoryRegion *mr = mri.second;
1027     mr->curPos = mr->origin;
1028   }
1029 }
1030
1031 static uint64_t getInitialDot() {
1032   // By default linker scripts use an initial value of 0 for '.',
1033   // but prefer -image-base if set.
1034   if (script->hasSectionsCommand)
1035     return config->imageBase ? *config->imageBase : 0;
1036
1037   uint64_t startAddr = UINT64_MAX;
1038   // The sections with -T<section> have been sorted in order of ascending
1039   // address. We must lower startAddr if the lowest -T<section address> as
1040   // calls to setDot() must be monotonically increasing.
1041   for (auto &kv : config->sectionStartMap)
1042     startAddr = std::min(startAddr, kv.second);
1043   return std::min(startAddr, target->getImageBase() + elf::getHeaderSize());
1044 }
1045
1046 // Here we assign addresses as instructed by linker script SECTIONS
1047 // sub-commands. Doing that allows us to use final VA values, so here
1048 // we also handle rest commands like symbol assignments and ASSERTs.
1049 void LinkerScript::assignAddresses() {
1050   dot = getInitialDot();
1051
1052   auto deleter = make_unique<AddressState>();
1053   ctx = deleter.get();
1054   errorOnMissingSection = true;
1055   switchTo(aether);
1056
1057   for (BaseCommand *base : sectionCommands) {
1058     if (auto *cmd = dyn_cast<SymbolAssignment>(base)) {
1059       cmd->addr = dot;
1060       assignSymbol(cmd, false);
1061       cmd->size = dot - cmd->addr;
1062       continue;
1063     }
1064     assignOffsets(cast<OutputSection>(base));
1065   }
1066   ctx = nullptr;
1067 }
1068
1069 // Creates program headers as instructed by PHDRS linker script command.
1070 std::vector<PhdrEntry *> LinkerScript::createPhdrs() {
1071   std::vector<PhdrEntry *> ret;
1072
1073   // Process PHDRS and FILEHDR keywords because they are not
1074   // real output sections and cannot be added in the following loop.
1075   for (const PhdrsCommand &cmd : phdrsCommands) {
1076     PhdrEntry *phdr = make<PhdrEntry>(cmd.type, cmd.flags ? *cmd.flags : PF_R);
1077
1078     if (cmd.hasFilehdr)
1079       phdr->add(Out::elfHeader);
1080     if (cmd.hasPhdrs)
1081       phdr->add(Out::programHeaders);
1082
1083     if (cmd.lmaExpr) {
1084       phdr->p_paddr = cmd.lmaExpr().getValue();
1085       phdr->hasLMA = true;
1086     }
1087     ret.push_back(phdr);
1088   }
1089
1090   // Add output sections to program headers.
1091   for (OutputSection *sec : outputSections) {
1092     // Assign headers specified by linker script
1093     for (size_t id : getPhdrIndices(sec)) {
1094       ret[id]->add(sec);
1095       if (!phdrsCommands[id].flags.hasValue())
1096         ret[id]->p_flags |= sec->getPhdrFlags();
1097     }
1098   }
1099   return ret;
1100 }
1101
1102 // Returns true if we should emit an .interp section.
1103 //
1104 // We usually do. But if PHDRS commands are given, and
1105 // no PT_INTERP is there, there's no place to emit an
1106 // .interp, so we don't do that in that case.
1107 bool LinkerScript::needsInterpSection() {
1108   if (phdrsCommands.empty())
1109     return true;
1110   for (PhdrsCommand &cmd : phdrsCommands)
1111     if (cmd.type == PT_INTERP)
1112       return true;
1113   return false;
1114 }
1115
1116 ExprValue LinkerScript::getSymbolValue(StringRef name, const Twine &loc) {
1117   if (name == ".") {
1118     if (ctx)
1119       return {ctx->outSec, false, dot - ctx->outSec->addr, loc};
1120     error(loc + ": unable to get location counter value");
1121     return 0;
1122   }
1123
1124   if (Symbol *sym = symtab->find(name)) {
1125     if (auto *ds = dyn_cast<Defined>(sym))
1126       return {ds->section, false, ds->value, loc};
1127     if (isa<SharedSymbol>(sym))
1128       if (!errorOnMissingSection)
1129         return {nullptr, false, 0, loc};
1130   }
1131
1132   error(loc + ": symbol not found: " + name);
1133   return 0;
1134 }
1135
1136 // Returns the index of the segment named Name.
1137 static Optional<size_t> getPhdrIndex(ArrayRef<PhdrsCommand> vec,
1138                                      StringRef name) {
1139   for (size_t i = 0; i < vec.size(); ++i)
1140     if (vec[i].name == name)
1141       return i;
1142   return None;
1143 }
1144
1145 // Returns indices of ELF headers containing specific section. Each index is a
1146 // zero based number of ELF header listed within PHDRS {} script block.
1147 std::vector<size_t> LinkerScript::getPhdrIndices(OutputSection *cmd) {
1148   std::vector<size_t> ret;
1149
1150   for (StringRef s : cmd->phdrs) {
1151     if (Optional<size_t> idx = getPhdrIndex(phdrsCommands, s))
1152       ret.push_back(*idx);
1153     else if (s != "NONE")
1154       error(cmd->location + ": section header '" + s +
1155             "' is not listed in PHDRS");
1156   }
1157   return ret;
1158 }