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

   1 //===- LinkerScript.cpp ---------------------------------------------------===//
   2 //
   3 //                             The LLVM Linker
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains the parser/evaluator of the linker script.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "LinkerScript.h"
  15 #include "Config.h"
  16 #include "InputSection.h"
  17 #include "OutputSections.h"
  18 #include "Strings.h"
  19 #include "SymbolTable.h"
  20 #include "Symbols.h"
  21 #include "SyntheticSections.h"
  22 #include "Target.h"
  23 #include "Writer.h"
  24 #include "lld/Common/Memory.h"
  25 #include "lld/Common/Threads.h"
  26 #include "llvm/ADT/STLExtras.h"
  27 #include "llvm/ADT/StringRef.h"
  28 #include "llvm/BinaryFormat/ELF.h"
  29 #include "llvm/Support/Casting.h"
  30 #include "llvm/Support/Endian.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/FileSystem.h"
  33 #include "llvm/Support/Path.h"
  34 #include <algorithm>
  35 #include <cassert>
  36 #include <cstddef>
  37 #include <cstdint>
  38 #include <iterator>
  39 #include <limits>
  40 #include <string>
  41 #include <vector>
  42
  43 using namespace llvm;
  44 using namespace llvm::ELF;
  45 using namespace llvm::object;
  46 using namespace llvm::support::endian;
  47 using namespace lld;
  48 using namespace lld::elf;
  49
  50 LinkerScript *elf::Script;
  51
  52 static uint64_t getOutputSectionVA(SectionBase *InputSec, StringRef Loc) {
  53   if (OutputSection *OS = InputSec->getOutputSection())
  54     return OS->Addr;
  55   error(Loc + ": unable to evaluate expression: input section " +
  56         InputSec->Name + " has no output section assigned");
  57   return 0;
  58 }
  59
  60 uint64_t ExprValue::getValue() const {
  61   if (Sec)
  62     return alignTo(Sec->getOffset(Val) + getOutputSectionVA(Sec, Loc),
  63                    Alignment);
  64   return alignTo(Val, Alignment);
  65 }
  66
  67 uint64_t ExprValue::getSecAddr() const {
  68   if (Sec)
  69     return Sec->getOffset(0) + getOutputSectionVA(Sec, Loc);
  70   return 0;
  71 }
  72
  73 uint64_t ExprValue::getSectionOffset() const {
  74   // If the alignment is trivial, we don't have to compute the full
  75   // value to know the offset. This allows this function to succeed in
  76   // cases where the output section is not yet known.
  77   if (Alignment == 1)
  78     return Val;
  79   return getValue() - getSecAddr();
  80 }
  81
  82 OutputSection *LinkerScript::createOutputSection(StringRef Name,
  83                                                  StringRef Location) {
  84   OutputSection *&SecRef = NameToOutputSection[Name];
  85   OutputSection *Sec;
  86   if (SecRef && SecRef->Location.empty()) {
  87     // There was a forward reference.
  88     Sec = SecRef;
  89   } else {
  90     Sec = make<OutputSection>(Name, SHT_NOBITS, 0);
  91     if (!SecRef)
  92       SecRef = Sec;
  93   }
  94   Sec->Location = Location;
  95   return Sec;
  96 }
  97
  98 OutputSection *LinkerScript::getOrCreateOutputSection(StringRef Name) {
  99   OutputSection *&CmdRef = NameToOutputSection[Name];
 100   if (!CmdRef)
 101     CmdRef = make<OutputSection>(Name, SHT_PROGBITS, 0);
 102   return CmdRef;
 103 }
 104
 105 void LinkerScript::setDot(Expr E, const Twine &Loc, bool InSec) {
 106   uint64_t Val = E().getValue();
 107   if (Val < Dot && InSec)
 108     error(Loc + ": unable to move location counter backward for: " +
 109           Ctx->OutSec->Name);
 110   Dot = Val;
 111
 112   // Update to location counter means update to section size.
 113   if (InSec)
 114     Ctx->OutSec->Size = Dot - Ctx->OutSec->Addr;
 115 }
 116
 117 // This function is called from processSectionCommands,
 118 // while we are fixing the output section layout.
 119 void LinkerScript::addSymbol(SymbolAssignment *Cmd) {
 120   if (Cmd->Name == ".")
 121     return;
 122
 123   // If a symbol was in PROVIDE(), we need to define it only when
 124   // it is a referenced undefined symbol.
 125   Symbol *B = Symtab->find(Cmd->Name);
 126   if (Cmd->Provide && (!B || B->isDefined()))
 127     return;
 128
 129   // Define a symbol.
 130   Symbol *Sym;
 131   uint8_t Visibility = Cmd->Hidden ? STV_HIDDEN : STV_DEFAULT;
 132   std::tie(Sym, std::ignore) = Symtab->insert(Cmd->Name, /*Type*/ 0, Visibility,
 133                                               /*CanOmitFromDynSym*/ false,
 134                                               /*File*/ nullptr);
 135   ExprValue Value = Cmd->Expression();
 136   SectionBase *Sec = Value.isAbsolute() ? nullptr : Value.Sec;
 137
 138   // When this function is called, section addresses have not been
 139   // fixed yet. So, we may or may not know the value of the RHS
 140   // expression.
 141   //
 142   // For example, if an expression is `x = 42`, we know x is always 42.
 143   // However, if an expression is `x = .`, there's no way to know its
 144   // value at the moment.
 145   //
 146   // We want to set symbol values early if we can. This allows us to
 147   // use symbols as variables in linker scripts. Doing so allows us to
 148   // write expressions like this: `alignment = 16; . = ALIGN(., alignment)`.
 149   uint64_t SymValue = Value.Sec ? 0 : Value.getValue();
 150
 151   replaceSymbol<Defined>(Sym, nullptr, Cmd->Name, STB_GLOBAL, Visibility,
 152                          STT_NOTYPE, SymValue, 0, Sec);
 153   Cmd->Sym = cast<Defined>(Sym);
 154 }
 155
 156 // This function is called from assignAddresses, while we are
 157 // fixing the output section addresses. This function is supposed
 158 // to set the final value for a given symbol assignment.
 159 void LinkerScript::assignSymbol(SymbolAssignment *Cmd, bool InSec) {
 160   if (Cmd->Name == ".") {
 161     setDot(Cmd->Expression, Cmd->Location, InSec);
 162     return;
 163   }
 164
 165   if (!Cmd->Sym)
 166     return;
 167
 168   ExprValue V = Cmd->Expression();
 169   if (V.isAbsolute()) {
 170     Cmd->Sym->Section = nullptr;
 171     Cmd->Sym->Value = V.getValue();
 172   } else {
 173     Cmd->Sym->Section = V.Sec;
 174     Cmd->Sym->Value = V.getSectionOffset();
 175   }
 176 }
 177
 178 static std::string getFilename(InputFile *File) {
 179   if (!File)
 180     return "";
 181   if (File->ArchiveName.empty())
 182     return File->getName();
 183   return (File->ArchiveName + "(" + File->getName() + ")").str();
 184 }
 185
 186 bool LinkerScript::shouldKeep(InputSectionBase *S) {
 187   if (KeptSections.empty())
 188     return false;
 189   std::string Filename = getFilename(S->File);
 190   for (InputSectionDescription *ID : KeptSections)
 191     if (ID->FilePat.match(Filename))
 192       for (SectionPattern &P : ID->SectionPatterns)
 193         if (P.SectionPat.match(S->Name))
 194           return true;
 195   return false;
 196 }
 197
 198 // A helper function for the SORT() command.
 199 static std::function<bool(InputSectionBase *, InputSectionBase *)>
 200 getComparator(SortSectionPolicy K) {
 201   switch (K) {
 202   case SortSectionPolicy::Alignment:
 203     return [](InputSectionBase *A, InputSectionBase *B) {
 204       // ">" is not a mistake. Sections with larger alignments are placed
 205       // before sections with smaller alignments in order to reduce the
 206       // amount of padding necessary. This is compatible with GNU.
 207       return A->Alignment > B->Alignment;
 208     };
 209   case SortSectionPolicy::Name:
 210     return [](InputSectionBase *A, InputSectionBase *B) {
 211       return A->Name < B->Name;
 212     };
 213   case SortSectionPolicy::Priority:
 214     return [](InputSectionBase *A, InputSectionBase *B) {
 215       return getPriority(A->Name) < getPriority(B->Name);
 216     };
 217   default:
 218     llvm_unreachable("unknown sort policy");
 219   }
 220 }
 221
 222 // A helper function for the SORT() command.
 223 static bool matchConstraints(ArrayRef<InputSection *> Sections,
 224                              ConstraintKind Kind) {
 225   if (Kind == ConstraintKind::NoConstraint)
 226     return true;
 227
 228   bool IsRW = llvm::any_of(
 229       Sections, [](InputSection *Sec) { return Sec->Flags & SHF_WRITE; });
 230
 231   return (IsRW && Kind == ConstraintKind::ReadWrite) ||
 232          (!IsRW && Kind == ConstraintKind::ReadOnly);
 233 }
 234
 235 static void sortSections(MutableArrayRef<InputSection *> Vec,
 236                          SortSectionPolicy K) {
 237   if (K != SortSectionPolicy::Default && K != SortSectionPolicy::None)
 238     std::stable_sort(Vec.begin(), Vec.end(), getComparator(K));
 239 }
 240
 241 // Sort sections as instructed by SORT-family commands and --sort-section
 242 // option. Because SORT-family commands can be nested at most two depth
 243 // (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
 244 // line option is respected even if a SORT command is given, the exact
 245 // behavior we have here is a bit complicated. Here are the rules.
 246 //
 247 // 1. If two SORT commands are given, --sort-section is ignored.
 248 // 2. If one SORT command is given, and if it is not SORT_NONE,
 249 //    --sort-section is handled as an inner SORT command.
 250 // 3. If one SORT command is given, and if it is SORT_NONE, don't sort.
 251 // 4. If no SORT command is given, sort according to --sort-section.
 252 // 5. If no SORT commands are given and --sort-section is not specified,
 253 //    apply sorting provided by --symbol-ordering-file if any exist.
 254 static void sortInputSections(
 255     MutableArrayRef<InputSection *> Vec, const SectionPattern &Pat,
 256     const DenseMap<SectionBase *, int> &Order) {
 257   if (Pat.SortOuter == SortSectionPolicy::None)
 258     return;
 259
 260   if (Pat.SortOuter == SortSectionPolicy::Default &&
 261       Config->SortSection == SortSectionPolicy::Default) {
 262     // If -symbol-ordering-file was given, sort accordingly.
 263     // Usually, Order is empty.
 264     if (!Order.empty())
 265       sortByOrder(Vec, [&](InputSectionBase *S) { return Order.lookup(S); });
 266     return;
 267   }
 268
 269   if (Pat.SortInner == SortSectionPolicy::Default)
 270     sortSections(Vec, Config->SortSection);
 271   else
 272     sortSections(Vec, Pat.SortInner);
 273   sortSections(Vec, Pat.SortOuter);
 274 }
 275
 276 // Compute and remember which sections the InputSectionDescription matches.
 277 std::vector<InputSection *>
 278 LinkerScript::computeInputSections(const InputSectionDescription *Cmd,
 279                                    const DenseMap<SectionBase *, int> &Order) {
 280   std::vector<InputSection *> Ret;
 281
 282   // Collects all sections that satisfy constraints of Cmd.
 283   for (const SectionPattern &Pat : Cmd->SectionPatterns) {
 284     size_t SizeBefore = Ret.size();
 285
 286     for (InputSectionBase *Sec : InputSections) {
 287       if (!Sec->Live || Sec->Assigned)
 288         continue;
 289
 290       // For -emit-relocs we have to ignore entries like
 291       //   .rela.dyn : { *(.rela.data) }
 292       // which are common because they are in the default bfd script.
 293       if (Sec->Type == SHT_REL || Sec->Type == SHT_RELA)
 294         continue;
 295
 296       std::string Filename = getFilename(Sec->File);
 297       if (!Cmd->FilePat.match(Filename) ||
 298           Pat.ExcludedFilePat.match(Filename) ||
 299           !Pat.SectionPat.match(Sec->Name))
 300         continue;
 301
 302       // It is safe to assume that Sec is an InputSection
 303       // because mergeable or EH input sections have already been
 304       // handled and eliminated.
 305       Ret.push_back(cast<InputSection>(Sec));
 306       Sec->Assigned = true;
 307     }
 308
 309     sortInputSections(MutableArrayRef<InputSection *>(Ret).slice(SizeBefore),
 310                       Pat, Order);
 311   }
 312   return Ret;
 313 }
 314
 315 void LinkerScript::discard(ArrayRef<InputSection *> V) {
 316   for (InputSection *S : V) {
 317     if (S == InX::ShStrTab || S == InX::Dynamic || S == InX::DynSymTab ||
 318         S == InX::DynStrTab)
 319       error("discarding " + S->Name + " section is not allowed");
 320
 321     S->Assigned = false;
 322     S->Live = false;
 323     discard(S->DependentSections);
 324   }
 325 }
 326
 327 std::vector<InputSection *> LinkerScript::createInputSectionList(
 328     OutputSection &OutCmd, const DenseMap<SectionBase *, int> &Order) {
 329   std::vector<InputSection *> Ret;
 330
 331   for (BaseCommand *Base : OutCmd.SectionCommands) {
 332     if (auto *Cmd = dyn_cast<InputSectionDescription>(Base)) {
 333       Cmd->Sections = computeInputSections(Cmd, Order);
 334       Ret.insert(Ret.end(), Cmd->Sections.begin(), Cmd->Sections.end());
 335     }
 336   }
 337   return Ret;
 338 }
 339
 340 void LinkerScript::processSectionCommands() {
 341   // A symbol can be assigned before any section is mentioned in the linker
 342   // script. In an DSO, the symbol values are addresses, so the only important
 343   // section values are:
 344   // * SHN_UNDEF
 345   // * SHN_ABS
 346   // * Any value meaning a regular section.
 347   // To handle that, create a dummy aether section that fills the void before
 348   // the linker scripts switches to another section. It has an index of one
 349   // which will map to whatever the first actual section is.
 350   Aether = make<OutputSection>("", 0, SHF_ALLOC);
 351   Aether->SectionIndex = 1;
 352
 353   // Ctx captures the local AddressState and makes it accessible deliberately.
 354   // This is needed as there are some cases where we cannot just
 355   // thread the current state through to a lambda function created by the
 356   // script parser.
 357   auto Deleter = make_unique<AddressState>();
 358   Ctx = Deleter.get();
 359   Ctx->OutSec = Aether;
 360
 361   size_t I = 0;
 362   DenseMap<SectionBase *, int> Order = buildSectionOrder();
 363   // Add input sections to output sections.
 364   for (BaseCommand *Base : SectionCommands) {
 365     // Handle symbol assignments outside of any output section.
 366     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
 367       addSymbol(Cmd);
 368       continue;
 369     }
 370
 371     if (auto *Sec = dyn_cast<OutputSection>(Base)) {
 372       std::vector<InputSection *> V = createInputSectionList(*Sec, Order);
 373
 374       // The output section name `/DISCARD/' is special.
 375       // Any input section assigned to it is discarded.
 376       if (Sec->Name == "/DISCARD/") {
 377         discard(V);
 378         continue;
 379       }
 380
 381       // This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive
 382       // ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input
 383       // sections satisfy a given constraint. If not, a directive is handled
 384       // as if it wasn't present from the beginning.
 385       //
 386       // Because we'll iterate over SectionCommands many more times, the easy
 387       // way to "make it as if it wasn't present" is to make it empty.
 388       if (!matchConstraints(V, Sec->Constraint)) {
 389         for (InputSectionBase *S : V)
 390           S->Assigned = false;
 391         Sec->SectionCommands.clear();
 392         continue;
 393       }
 394
 395       // A directive may contain symbol definitions like this:
 396       // ".foo : { ...; bar = .; }". Handle them.
 397       for (BaseCommand *Base : Sec->SectionCommands)
 398         if (auto *OutCmd = dyn_cast<SymbolAssignment>(Base))
 399           addSymbol(OutCmd);
 400
 401       // Handle subalign (e.g. ".foo : SUBALIGN(32) { ... }"). If subalign
 402       // is given, input sections are aligned to that value, whether the
 403       // given value is larger or smaller than the original section alignment.
 404       if (Sec->SubalignExpr) {
 405         uint32_t Subalign = Sec->SubalignExpr().getValue();
 406         for (InputSectionBase *S : V)
 407           S->Alignment = Subalign;
 408       }
 409
 410       // Add input sections to an output section.
 411       for (InputSection *S : V)
 412         Sec->addSection(S);
 413
 414       Sec->SectionIndex = I++;
 415       if (Sec->Noload)
 416         Sec->Type = SHT_NOBITS;
 417     }
 418   }
 419   Ctx = nullptr;
 420 }
 421
 422 static OutputSection *findByName(ArrayRef<BaseCommand *> Vec,
 423                                  StringRef Name) {
 424   for (BaseCommand *Base : Vec)
 425     if (auto *Sec = dyn_cast<OutputSection>(Base))
 426       if (Sec->Name == Name)
 427         return Sec;
 428   return nullptr;
 429 }
 430
 431 static OutputSection *createSection(InputSectionBase *IS,
 432                                     StringRef OutsecName) {
 433   OutputSection *Sec = Script->createOutputSection(OutsecName, "<internal>");
 434   Sec->addSection(cast<InputSection>(IS));
 435   return Sec;
 436 }
 437
 438 static OutputSection *addInputSec(StringMap<OutputSection *> &Map,
 439                                   InputSectionBase *IS, StringRef OutsecName) {
 440   // Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r
 441   // option is given. A section with SHT_GROUP defines a "section group", and
 442   // its members have SHF_GROUP attribute. Usually these flags have already been
 443   // stripped by InputFiles.cpp as section groups are processed and uniquified.
 444   // However, for the -r option, we want to pass through all section groups
 445   // as-is because adding/removing members or merging them with other groups
 446   // change their semantics.
 447   if (IS->Type == SHT_GROUP || (IS->Flags & SHF_GROUP))
 448     return createSection(IS, OutsecName);
 449
 450   // Imagine .zed : { *(.foo) *(.bar) } script. Both foo and bar may have
 451   // relocation sections .rela.foo and .rela.bar for example. Most tools do
 452   // not allow multiple REL[A] sections for output section. Hence we
 453   // should combine these relocation sections into single output.
 454   // We skip synthetic sections because it can be .rela.dyn/.rela.plt or any
 455   // other REL[A] sections created by linker itself.
 456   if (!isa<SyntheticSection>(IS) &&
 457       (IS->Type == SHT_REL || IS->Type == SHT_RELA)) {
 458     auto *Sec = cast<InputSection>(IS);
 459     OutputSection *Out = Sec->getRelocatedSection()->getOutputSection();
 460
 461     if (Out->RelocationSection) {
 462       Out->RelocationSection->addSection(Sec);
 463       return nullptr;
 464     }
 465
 466     Out->RelocationSection = createSection(IS, OutsecName);
 467     return Out->RelocationSection;
 468   }
 469
 470   // When control reaches here, mergeable sections have already been merged into
 471   // synthetic sections. For relocatable case we want to create one output
 472   // section per syntetic section so that they have a valid sh_entsize.
 473   if (Config->Relocatable && (IS->Flags & SHF_MERGE))
 474     return createSection(IS, OutsecName);
 475
 476   //  The ELF spec just says
 477   // ----------------------------------------------------------------
 478   // In the first phase, input sections that match in name, type and
 479   // attribute flags should be concatenated into single sections.
 480   // ----------------------------------------------------------------
 481   //
 482   // However, it is clear that at least some flags have to be ignored for
 483   // section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be
 484   // ignored. We should not have two output .text sections just because one was
 485   // in a group and another was not for example.
 486   //
 487   // It also seems that that wording was a late addition and didn't get the
 488   // necessary scrutiny.
 489   //
 490   // Merging sections with different flags is expected by some users. One
 491   // reason is that if one file has
 492   //
 493   // int *const bar __attribute__((section(".foo"))) = (int *)0;
 494   //
 495   // gcc with -fPIC will produce a read only .foo section. But if another
 496   // file has
 497   //
 498   // int zed;
 499   // int *const bar __attribute__((section(".foo"))) = (int *)&zed;
 500   //
 501   // gcc with -fPIC will produce a read write section.
 502   //
 503   // Last but not least, when using linker script the merge rules are forced by
 504   // the script. Unfortunately, linker scripts are name based. This means that
 505   // expressions like *(.foo*) can refer to multiple input sections with
 506   // different flags. We cannot put them in different output sections or we
 507   // would produce wrong results for
 508   //
 509   // start = .; *(.foo.*) end = .; *(.bar)
 510   //
 511   // and a mapping of .foo1 and .bar1 to one section and .foo2 and .bar2 to
 512   // another. The problem is that there is no way to layout those output
 513   // sections such that the .foo sections are the only thing between the start
 514   // and end symbols.
 515   //
 516   // Given the above issues, we instead merge sections by name and error on
 517   // incompatible types and flags.
 518   OutputSection *&Sec = Map[OutsecName];
 519   if (Sec) {
 520     Sec->addSection(cast<InputSection>(IS));
 521     return nullptr;
 522   }
 523
 524   Sec = createSection(IS, OutsecName);
 525   return Sec;
 526 }
 527
 528 // Add sections that didn't match any sections command.
 529 void LinkerScript::addOrphanSections() {
 530   unsigned End = SectionCommands.size();
 531   StringMap<OutputSection *> Map;
 532
 533   std::vector<OutputSection *> V;
 534   for (InputSectionBase *S : InputSections) {
 535     if (!S->Live || S->Parent)
 536       continue;
 537
 538     StringRef Name = getOutputSectionName(S);
 539
 540     if (Config->OrphanHandling == OrphanHandlingPolicy::Error)
 541       error(toString(S) + " is being placed in '" + Name + "'");
 542     else if (Config->OrphanHandling == OrphanHandlingPolicy::Warn)
 543       warn(toString(S) + " is being placed in '" + Name + "'");
 544
 545     if (OutputSection *Sec =
 546             findByName(makeArrayRef(SectionCommands).slice(0, End), Name)) {
 547       Sec->addSection(cast<InputSection>(S));
 548       continue;
 549     }
 550
 551     if (OutputSection *OS = addInputSec(Map, S, Name))
 552       V.push_back(OS);
 553     assert(S->getOutputSection()->SectionIndex == INT_MAX);
 554   }
 555
 556   // If no SECTIONS command was given, we should insert sections commands
 557   // before others, so that we can handle scripts which refers them,
 558   // for example: "foo = ABSOLUTE(ADDR(.text)));".
 559   // When SECTIONS command is present we just add all orphans to the end.
 560   if (HasSectionsCommand)
 561     SectionCommands.insert(SectionCommands.end(), V.begin(), V.end());
 562   else
 563     SectionCommands.insert(SectionCommands.begin(), V.begin(), V.end());
 564 }
 565
 566 uint64_t LinkerScript::advance(uint64_t Size, unsigned Alignment) {
 567   bool IsTbss =
 568       (Ctx->OutSec->Flags & SHF_TLS) && Ctx->OutSec->Type == SHT_NOBITS;
 569   uint64_t Start = IsTbss ? Dot + Ctx->ThreadBssOffset : Dot;
 570   Start = alignTo(Start, Alignment);
 571   uint64_t End = Start + Size;
 572
 573   if (IsTbss)
 574     Ctx->ThreadBssOffset = End - Dot;
 575   else
 576     Dot = End;
 577   return End;
 578 }
 579
 580 void LinkerScript::output(InputSection *S) {
 581   uint64_t Before = advance(0, 1);
 582   uint64_t Pos = advance(S->getSize(), S->Alignment);
 583   S->OutSecOff = Pos - S->getSize() - Ctx->OutSec->Addr;
 584
 585   // Update output section size after adding each section. This is so that
 586   // SIZEOF works correctly in the case below:
 587   // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
 588   Ctx->OutSec->Size = Pos - Ctx->OutSec->Addr;
 589
 590   // If there is a memory region associated with this input section, then
 591   // place the section in that region and update the region index.
 592   if (Ctx->LMARegion)
 593     Ctx->LMARegion->CurPos += Pos - Before;
 594   // FIXME: should we also produce overflow errors for LMARegion?
 595
 596   if (Ctx->MemRegion) {
 597     uint64_t &CurOffset = Ctx->MemRegion->CurPos;
 598     CurOffset += Pos - Before;
 599     uint64_t CurSize = CurOffset - Ctx->MemRegion->Origin;
 600     if (CurSize > Ctx->MemRegion->Length) {
 601       uint64_t OverflowAmt = CurSize - Ctx->MemRegion->Length;
 602       error("section '" + Ctx->OutSec->Name + "' will not fit in region '" +
 603             Ctx->MemRegion->Name + "': overflowed by " + Twine(OverflowAmt) +
 604             " bytes");
 605     }
 606   }
 607 }
 608
 609 void LinkerScript::switchTo(OutputSection *Sec) {
 610   if (Ctx->OutSec == Sec)
 611     return;
 612
 613   Ctx->OutSec = Sec;
 614   Ctx->OutSec->Addr = advance(0, Ctx->OutSec->Alignment);
 615 }
 616
 617 // This function searches for a memory region to place the given output
 618 // section in. If found, a pointer to the appropriate memory region is
 619 // returned. Otherwise, a nullptr is returned.
 620 MemoryRegion *LinkerScript::findMemoryRegion(OutputSection *Sec) {
 621   // If a memory region name was specified in the output section command,
 622   // then try to find that region first.
 623   if (!Sec->MemoryRegionName.empty()) {
 624     if (MemoryRegion *M = MemoryRegions.lookup(Sec->MemoryRegionName))
 625       return M;
 626     error("memory region '" + Sec->MemoryRegionName + "' not declared");
 627     return nullptr;
 628   }
 629
 630   // If at least one memory region is defined, all sections must
 631   // belong to some memory region. Otherwise, we don't need to do
 632   // anything for memory regions.
 633   if (MemoryRegions.empty())
 634     return nullptr;
 635
 636   // See if a region can be found by matching section flags.
 637   for (auto &Pair : MemoryRegions) {
 638     MemoryRegion *M = Pair.second;
 639     if ((M->Flags & Sec->Flags) && (M->NegFlags & Sec->Flags) == 0)
 640       return M;
 641   }
 642
 643   // Otherwise, no suitable region was found.
 644   if (Sec->Flags & SHF_ALLOC)
 645     error("no memory region specified for section '" + Sec->Name + "'");
 646   return nullptr;
 647 }
 648
 649 // This function assigns offsets to input sections and an output section
 650 // for a single sections command (e.g. ".text { *(.text); }").
 651 void LinkerScript::assignOffsets(OutputSection *Sec) {
 652   if (!(Sec->Flags & SHF_ALLOC))
 653     Dot = 0;
 654   else if (Sec->AddrExpr)
 655     setDot(Sec->AddrExpr, Sec->Location, false);
 656
 657   Ctx->MemRegion = Sec->MemRegion;
 658   Ctx->LMARegion = Sec->LMARegion;
 659   if (Ctx->MemRegion)
 660     Dot = Ctx->MemRegion->CurPos;
 661
 662   switchTo(Sec);
 663
 664   if (Sec->LMAExpr)
 665     Ctx->LMAOffset = Sec->LMAExpr().getValue() - Dot;
 666
 667   if (MemoryRegion *MR = Sec->LMARegion)
 668     Ctx->LMAOffset = MR->CurPos - Dot;
 669
 670   // If neither AT nor AT> is specified for an allocatable section, the linker
 671   // will set the LMA such that the difference between VMA and LMA for the
 672   // section is the same as the preceding output section in the same region
 673   // https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html
 674   if (PhdrEntry *L = Ctx->OutSec->PtLoad)
 675     L->LMAOffset = Ctx->LMAOffset;
 676
 677   // The Size previously denoted how many InputSections had been added to this
 678   // section, and was used for sorting SHF_LINK_ORDER sections. Reset it to
 679   // compute the actual size value.
 680   Sec->Size = 0;
 681
 682   // We visited SectionsCommands from processSectionCommands to
 683   // layout sections. Now, we visit SectionsCommands again to fix
 684   // section offsets.
 685   for (BaseCommand *Base : Sec->SectionCommands) {
 686     // This handles the assignments to symbol or to the dot.
 687     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
 688       assignSymbol(Cmd, true);
 689       continue;
 690     }
 691
 692     // Handle BYTE(), SHORT(), LONG(), or QUAD().
 693     if (auto *Cmd = dyn_cast<ByteCommand>(Base)) {
 694       Cmd->Offset = Dot - Ctx->OutSec->Addr;
 695       Dot += Cmd->Size;
 696       if (Ctx->MemRegion)
 697         Ctx->MemRegion->CurPos += Cmd->Size;
 698       if (Ctx->LMARegion)
 699         Ctx->LMARegion->CurPos += Cmd->Size;
 700       Ctx->OutSec->Size = Dot - Ctx->OutSec->Addr;
 701       continue;
 702     }
 703
 704     // Handle ASSERT().
 705     if (auto *Cmd = dyn_cast<AssertCommand>(Base)) {
 706       Cmd->Expression();
 707       continue;
 708     }
 709
 710     // Handle a single input section description command.
 711     // It calculates and assigns the offsets for each section and also
 712     // updates the output section size.
 713     auto *Cmd = cast<InputSectionDescription>(Base);
 714     for (InputSection *Sec : Cmd->Sections) {
 715       // We tentatively added all synthetic sections at the beginning and
 716       // removed empty ones afterwards (because there is no way to know
 717       // whether they were going be empty or not other than actually running
 718       // linker scripts.) We need to ignore remains of empty sections.
 719       if (auto *S = dyn_cast<SyntheticSection>(Sec))
 720         if (S->empty())
 721           continue;
 722
 723       if (!Sec->Live)
 724         continue;
 725       assert(Ctx->OutSec == Sec->getParent());
 726       output(Sec);
 727     }
 728   }
 729 }
 730
 731 void LinkerScript::removeEmptyCommands() {
 732   // It is common practice to use very generic linker scripts. So for any
 733   // given run some of the output sections in the script will be empty.
 734   // We could create corresponding empty output sections, but that would
 735   // clutter the output.
 736   // We instead remove trivially empty sections. The bfd linker seems even
 737   // more aggressive at removing them.
 738   llvm::erase_if(SectionCommands, [&](BaseCommand *Base) {
 739     if (auto *Sec = dyn_cast<OutputSection>(Base))
 740       return !Sec->Live;
 741     return false;
 742   });
 743 }
 744
 745 static bool isAllSectionDescription(const OutputSection &Cmd) {
 746   for (BaseCommand *Base : Cmd.SectionCommands)
 747     if (!isa<InputSectionDescription>(*Base))
 748       return false;
 749   return true;
 750 }
 751
 752 void LinkerScript::adjustSectionsBeforeSorting() {
 753   // If the output section contains only symbol assignments, create a
 754   // corresponding output section. The issue is what to do with linker script
 755   // like ".foo : { symbol = 42; }". One option would be to convert it to
 756   // "symbol = 42;". That is, move the symbol out of the empty section
 757   // description. That seems to be what bfd does for this simple case. The
 758   // problem is that this is not completely general. bfd will give up and
 759   // create a dummy section too if there is a ". = . + 1" inside the section
 760   // for example.
 761   // Given that we want to create the section, we have to worry what impact
 762   // it will have on the link. For example, if we just create a section with
 763   // 0 for flags, it would change which PT_LOADs are created.
 764   // We could remember that that particular section is dummy and ignore it in
 765   // other parts of the linker, but unfortunately there are quite a few places
 766   // that would need to change:
 767   //   * The program header creation.
 768   //   * The orphan section placement.
 769   //   * The address assignment.
 770   // The other option is to pick flags that minimize the impact the section
 771   // will have on the rest of the linker. That is why we copy the flags from
 772   // the previous sections. Only a few flags are needed to keep the impact low.
 773   uint64_t Flags = SHF_ALLOC;
 774
 775   for (BaseCommand *Cmd : SectionCommands) {
 776     auto *Sec = dyn_cast<OutputSection>(Cmd);
 777     if (!Sec)
 778       continue;
 779     if (Sec->Live) {
 780       Flags = Sec->Flags & (SHF_ALLOC | SHF_WRITE | SHF_EXECINSTR);
 781       continue;
 782     }
 783
 784     if (isAllSectionDescription(*Sec))
 785       continue;
 786
 787     Sec->Live = true;
 788     Sec->Flags = Flags;
 789   }
 790 }
 791
 792 void LinkerScript::adjustSectionsAfterSorting() {
 793   // Try and find an appropriate memory region to assign offsets in.
 794   for (BaseCommand *Base : SectionCommands) {
 795     if (auto *Sec = dyn_cast<OutputSection>(Base)) {
 796       if (!Sec->Live)
 797         continue;
 798       if (!Sec->LMARegionName.empty()) {
 799         if (MemoryRegion *M = MemoryRegions.lookup(Sec->LMARegionName))
 800           Sec->LMARegion = M;
 801         else
 802           error("memory region '" + Sec->LMARegionName + "' not declared");
 803       }
 804       Sec->MemRegion = findMemoryRegion(Sec);
 805       // Handle align (e.g. ".foo : ALIGN(16) { ... }").
 806       if (Sec->AlignExpr)
 807         Sec->Alignment =
 808             std::max<uint32_t>(Sec->Alignment, Sec->AlignExpr().getValue());
 809     }
 810   }
 811
 812   // If output section command doesn't specify any segments,
 813   // and we haven't previously assigned any section to segment,
 814   // then we simply assign section to the very first load segment.
 815   // Below is an example of such linker script:
 816   // PHDRS { seg PT_LOAD; }
 817   // SECTIONS { .aaa : { *(.aaa) } }
 818   std::vector<StringRef> DefPhdrs;
 819   auto FirstPtLoad =
 820       std::find_if(PhdrsCommands.begin(), PhdrsCommands.end(),
 821                    [](const PhdrsCommand &Cmd) { return Cmd.Type == PT_LOAD; });
 822   if (FirstPtLoad != PhdrsCommands.end())
 823     DefPhdrs.push_back(FirstPtLoad->Name);
 824
 825   // Walk the commands and propagate the program headers to commands that don't
 826   // explicitly specify them.
 827   for (BaseCommand *Base : SectionCommands) {
 828     auto *Sec = dyn_cast<OutputSection>(Base);
 829     if (!Sec)
 830       continue;
 831
 832     if (Sec->Phdrs.empty()) {
 833       // To match the bfd linker script behaviour, only propagate program
 834       // headers to sections that are allocated.
 835       if (Sec->Flags & SHF_ALLOC)
 836         Sec->Phdrs = DefPhdrs;
 837     } else {
 838       DefPhdrs = Sec->Phdrs;
 839     }
 840   }
 841 }
 842
 843 static OutputSection *findFirstSection(PhdrEntry *Load) {
 844   for (OutputSection *Sec : OutputSections)
 845     if (Sec->PtLoad == Load)
 846       return Sec;
 847   return nullptr;
 848 }
 849
 850 // Try to find an address for the file and program headers output sections,
 851 // which were unconditionally added to the first PT_LOAD segment earlier.
 852 //
 853 // When using the default layout, we check if the headers fit below the first
 854 // allocated section. When using a linker script, we also check if the headers
 855 // are covered by the output section. This allows omitting the headers by not
 856 // leaving enough space for them in the linker script; this pattern is common
 857 // in embedded systems.
 858 //
 859 // If there isn't enough space for these sections, we'll remove them from the
 860 // PT_LOAD segment, and we'll also remove the PT_PHDR segment.
 861 void LinkerScript::allocateHeaders(std::vector<PhdrEntry *> &Phdrs) {
 862   uint64_t Min = std::numeric_limits<uint64_t>::max();
 863   for (OutputSection *Sec : OutputSections)
 864     if (Sec->Flags & SHF_ALLOC)
 865       Min = std::min<uint64_t>(Min, Sec->Addr);
 866
 867   auto It = llvm::find_if(
 868       Phdrs, [](const PhdrEntry *E) { return E->p_type == PT_LOAD; });
 869   if (It == Phdrs.end())
 870     return;
 871   PhdrEntry *FirstPTLoad = *It;
 872
 873   uint64_t HeaderSize = getHeaderSize();
 874   // When linker script with SECTIONS is being used, don't output headers
 875   // unless there's a space for them.
 876   uint64_t Base = HasSectionsCommand ? alignDown(Min, Config->MaxPageSize) : 0;
 877   if (HeaderSize <= Min - Base || Script->hasPhdrsCommands()) {
 878     Min = alignDown(Min - HeaderSize, Config->MaxPageSize);
 879     Out::ElfHeader->Addr = Min;
 880     Out::ProgramHeaders->Addr = Min + Out::ElfHeader->Size;
 881     return;
 882   }
 883
 884   Out::ElfHeader->PtLoad = nullptr;
 885   Out::ProgramHeaders->PtLoad = nullptr;
 886   FirstPTLoad->FirstSec = findFirstSection(FirstPTLoad);
 887
 888   llvm::erase_if(Phdrs,
 889                  [](const PhdrEntry *E) { return E->p_type == PT_PHDR; });
 890 }
 891
 892 LinkerScript::AddressState::AddressState() {
 893   for (auto &MRI : Script->MemoryRegions) {
 894     MemoryRegion *MR = MRI.second;
 895     MR->CurPos = MR->Origin;
 896   }
 897 }
 898
 899 static uint64_t getInitialDot() {
 900   // By default linker scripts use an initial value of 0 for '.',
 901   // but prefer -image-base if set.
 902   if (Script->HasSectionsCommand)
 903     return Config->ImageBase ? *Config->ImageBase : 0;
 904
 905   uint64_t StartAddr = UINT64_MAX;
 906   // The Sections with -T<section> have been sorted in order of ascending
 907   // address. We must lower StartAddr if the lowest -T<section address> as
 908   // calls to setDot() must be monotonically increasing.
 909   for (auto &KV : Config->SectionStartMap)
 910     StartAddr = std::min(StartAddr, KV.second);
 911   return std::min(StartAddr, Target->getImageBase() + elf::getHeaderSize());
 912 }
 913
 914 // Here we assign addresses as instructed by linker script SECTIONS
 915 // sub-commands. Doing that allows us to use final VA values, so here
 916 // we also handle rest commands like symbol assignments and ASSERTs.
 917 void LinkerScript::assignAddresses() {
 918   Dot = getInitialDot();
 919
 920   auto Deleter = make_unique<AddressState>();
 921   Ctx = Deleter.get();
 922   ErrorOnMissingSection = true;
 923   switchTo(Aether);
 924
 925   for (BaseCommand *Base : SectionCommands) {
 926     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
 927       assignSymbol(Cmd, false);
 928       continue;
 929     }
 930
 931     if (auto *Cmd = dyn_cast<AssertCommand>(Base)) {
 932       Cmd->Expression();
 933       continue;
 934     }
 935
 936     assignOffsets(cast<OutputSection>(Base));
 937   }
 938   Ctx = nullptr;
 939 }
 940
 941 // Creates program headers as instructed by PHDRS linker script command.
 942 std::vector<PhdrEntry *> LinkerScript::createPhdrs() {
 943   std::vector<PhdrEntry *> Ret;
 944
 945   // Process PHDRS and FILEHDR keywords because they are not
 946   // real output sections and cannot be added in the following loop.
 947   for (const PhdrsCommand &Cmd : PhdrsCommands) {
 948     PhdrEntry *Phdr = make<PhdrEntry>(Cmd.Type, Cmd.Flags ? *Cmd.Flags : PF_R);
 949
 950     if (Cmd.HasFilehdr)
 951       Phdr->add(Out::ElfHeader);
 952     if (Cmd.HasPhdrs)
 953       Phdr->add(Out::ProgramHeaders);
 954
 955     if (Cmd.LMAExpr) {
 956       Phdr->p_paddr = Cmd.LMAExpr().getValue();
 957       Phdr->HasLMA = true;
 958     }
 959     Ret.push_back(Phdr);
 960   }
 961
 962   // Add output sections to program headers.
 963   for (OutputSection *Sec : OutputSections) {
 964     // Assign headers specified by linker script
 965     for (size_t Id : getPhdrIndices(Sec)) {
 966       Ret[Id]->add(Sec);
 967       if (!PhdrsCommands[Id].Flags.hasValue())
 968         Ret[Id]->p_flags |= Sec->getPhdrFlags();
 969     }
 970   }
 971   return Ret;
 972 }
 973
 974 // Returns true if we should emit an .interp section.
 975 //
 976 // We usually do. But if PHDRS commands are given, and
 977 // no PT_INTERP is there, there's no place to emit an
 978 // .interp, so we don't do that in that case.
 979 bool LinkerScript::needsInterpSection() {
 980   if (PhdrsCommands.empty())
 981     return true;
 982   for (PhdrsCommand &Cmd : PhdrsCommands)
 983     if (Cmd.Type == PT_INTERP)
 984       return true;
 985   return false;
 986 }
 987
 988 ExprValue LinkerScript::getSymbolValue(StringRef Name, const Twine &Loc) {
 989   if (Name == ".") {
 990     if (Ctx)
 991       return {Ctx->OutSec, false, Dot - Ctx->OutSec->Addr, Loc};
 992     error(Loc + ": unable to get location counter value");
 993     return 0;
 994   }
 995
 996   if (Symbol *Sym = Symtab->find(Name)) {
 997     if (auto *DS = dyn_cast<Defined>(Sym))
 998       return {DS->Section, false, DS->Value, Loc};
 999     if (auto *SS = dyn_cast<SharedSymbol>(Sym))
1000       if (!ErrorOnMissingSection || SS->CopyRelSec)
1001         return {SS->CopyRelSec, false, 0, Loc};
1002   }
1003
1004   error(Loc + ": symbol not found: " + Name);
1005   return 0;
1006 }
1007
1008 // Returns the index of the segment named Name.
1009 static Optional<size_t> getPhdrIndex(ArrayRef<PhdrsCommand> Vec,
1010                                      StringRef Name) {
1011   for (size_t I = 0; I < Vec.size(); ++I)
1012     if (Vec[I].Name == Name)
1013       return I;
1014   return None;
1015 }
1016
1017 // Returns indices of ELF headers containing specific section. Each index is a
1018 // zero based number of ELF header listed within PHDRS {} script block.
1019 std::vector<size_t> LinkerScript::getPhdrIndices(OutputSection *Cmd) {
1020   std::vector<size_t> Ret;
1021
1022   for (StringRef S : Cmd->Phdrs) {
1023     if (Optional<size_t> Idx = getPhdrIndex(PhdrsCommands, S))
1024       Ret.push_back(*Idx);
1025     else if (S != "NONE")
1026       error(Cmd->Location + ": section header '" + S +
1027             "' is not listed in PHDRS");
1028   }
1029   return Ret;
1030 }