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 "SymbolTable.h"
  19 #include "Symbols.h"
  20 #include "SyntheticSections.h"
  21 #include "Target.h"
  22 #include "Writer.h"
  23 #include "lld/Common/Memory.h"
  24 #include "lld/Common/Strings.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 && (!Sec || !Sec->getOutputSection()))
  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 // Expands the memory region by the specified size.
 106 static void expandMemoryRegion(MemoryRegion *MemRegion, uint64_t Size,
 107                                StringRef RegionName, StringRef SecName) {
 108   MemRegion->CurPos += Size;
 109   uint64_t NewSize = MemRegion->CurPos - MemRegion->Origin;
 110   if (NewSize > MemRegion->Length)
 111     error("section '" + SecName + "' will not fit in region '" + RegionName +
 112           "': overflowed by " + Twine(NewSize - MemRegion->Length) + " bytes");
 113 }
 114
 115 void LinkerScript::expandMemoryRegions(uint64_t Size) {
 116   if (Ctx->MemRegion)
 117     expandMemoryRegion(Ctx->MemRegion, Size, Ctx->MemRegion->Name,
 118                        Ctx->OutSec->Name);
 119   if (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   else
 139     expandMemoryRegions(Val - Dot);
 140
 141   Dot = Val;
 142 }
 143
 144 // Used for handling linker symbol assignments, for both finalizing
 145 // their values and doing early declarations. Returns true if symbol
 146 // should be defined from linker script.
 147 static bool shouldDefineSym(SymbolAssignment *Cmd) {
 148   if (Cmd->Name == ".")
 149     return false;
 150
 151   if (!Cmd->Provide)
 152     return true;
 153
 154   // If a symbol was in PROVIDE(), we need to define it only
 155   // when it is a referenced undefined symbol.
 156   Symbol *B = Symtab->find(Cmd->Name);
 157   if (B && !B->isDefined())
 158     return true;
 159   return false;
 160 }
 161
 162 // This function is called from processSectionCommands,
 163 // while we are fixing the output section layout.
 164 void LinkerScript::addSymbol(SymbolAssignment *Cmd) {
 165   if (!shouldDefineSym(Cmd))
 166     return;
 167
 168   // Define a symbol.
 169   Symbol *Sym;
 170   uint8_t Visibility = Cmd->Hidden ? STV_HIDDEN : STV_DEFAULT;
 171   std::tie(Sym, std::ignore) = Symtab->insert(Cmd->Name, /*Type*/ 0, Visibility,
 172                                               /*CanOmitFromDynSym*/ false,
 173                                               /*File*/ nullptr);
 174   ExprValue Value = Cmd->Expression();
 175   SectionBase *Sec = Value.isAbsolute() ? nullptr : Value.Sec;
 176
 177   // When this function is called, section addresses have not been
 178   // fixed yet. So, we may or may not know the value of the RHS
 179   // expression.
 180   //
 181   // For example, if an expression is `x = 42`, we know x is always 42.
 182   // However, if an expression is `x = .`, there's no way to know its
 183   // value at the moment.
 184   //
 185   // We want to set symbol values early if we can. This allows us to
 186   // use symbols as variables in linker scripts. Doing so allows us to
 187   // write expressions like this: `alignment = 16; . = ALIGN(., alignment)`.
 188   uint64_t SymValue = Value.Sec ? 0 : Value.getValue();
 189
 190   replaceSymbol<Defined>(Sym, nullptr, Cmd->Name, STB_GLOBAL, Visibility,
 191                          STT_NOTYPE, SymValue, 0, Sec);
 192   Cmd->Sym = cast<Defined>(Sym);
 193 }
 194
 195 // This function is called from LinkerScript::declareSymbols.
 196 // It creates a placeholder symbol if needed.
 197 static void declareSymbol(SymbolAssignment *Cmd) {
 198   if (!shouldDefineSym(Cmd))
 199     return;
 200
 201   // We can't calculate final value right now.
 202   Symbol *Sym;
 203   uint8_t Visibility = Cmd->Hidden ? STV_HIDDEN : STV_DEFAULT;
 204   std::tie(Sym, std::ignore) = Symtab->insert(Cmd->Name, /*Type*/ 0, Visibility,
 205                                               /*CanOmitFromDynSym*/ false,
 206                                               /*File*/ nullptr);
 207   replaceSymbol<Defined>(Sym, nullptr, Cmd->Name, STB_GLOBAL, Visibility,
 208                          STT_NOTYPE, 0, 0, nullptr);
 209   Cmd->Sym = cast<Defined>(Sym);
 210   Cmd->Provide = false;
 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     std::stable_sort(Vec.begin(), Vec.end(), 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->Live || 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 *IS = dyn_cast<InputSection>(Sec))
 392         if (IS->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 == InX::ShStrTab || S == InX::Dynamic || S == InX::DynSymTab ||
 417         S == InX::DynStrTab || S == InX::RelaPlt || S == InX::RelaDyn ||
 418         S == InX::RelrDyn)
 419       error("discarding " + S->Name + " section is not allowed");
 420
 421     // You can discard .hash and .gnu.hash sections by linker scripts. Since
 422     // they are synthesized sections, we need to handle them differently than
 423     // other regular sections.
 424     if (S == InX::GnuHashTab)
 425       InX::GnuHashTab = nullptr;
 426     if (S == InX::HashTab)
 427       InX::HashTab = nullptr;
 428
 429     S->Assigned = false;
 430     S->Live = false;
 431     discard(S->DependentSections);
 432   }
 433 }
 434
 435 std::vector<InputSection *>
 436 LinkerScript::createInputSectionList(OutputSection &OutCmd) {
 437   std::vector<InputSection *> Ret;
 438
 439   for (BaseCommand *Base : OutCmd.SectionCommands) {
 440     if (auto *Cmd = dyn_cast<InputSectionDescription>(Base)) {
 441       Cmd->Sections = computeInputSections(Cmd);
 442       Ret.insert(Ret.end(), Cmd->Sections.begin(), Cmd->Sections.end());
 443     }
 444   }
 445   return Ret;
 446 }
 447
 448 void LinkerScript::processSectionCommands() {
 449   // A symbol can be assigned before any section is mentioned in the linker
 450   // script. In an DSO, the symbol values are addresses, so the only important
 451   // section values are:
 452   // * SHN_UNDEF
 453   // * SHN_ABS
 454   // * Any value meaning a regular section.
 455   // To handle that, create a dummy aether section that fills the void before
 456   // the linker scripts switches to another section. It has an index of one
 457   // which will map to whatever the first actual section is.
 458   Aether = make<OutputSection>("", 0, SHF_ALLOC);
 459   Aether->SectionIndex = 1;
 460
 461   // Ctx captures the local AddressState and makes it accessible deliberately.
 462   // This is needed as there are some cases where we cannot just
 463   // thread the current state through to a lambda function created by the
 464   // script parser.
 465   auto Deleter = make_unique<AddressState>();
 466   Ctx = Deleter.get();
 467   Ctx->OutSec = Aether;
 468
 469   size_t I = 0;
 470   // Add input sections to output sections.
 471   for (BaseCommand *Base : SectionCommands) {
 472     // Handle symbol assignments outside of any output section.
 473     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
 474       addSymbol(Cmd);
 475       continue;
 476     }
 477
 478     if (auto *Sec = dyn_cast<OutputSection>(Base)) {
 479       std::vector<InputSection *> V = createInputSectionList(*Sec);
 480
 481       // The output section name `/DISCARD/' is special.
 482       // Any input section assigned to it is discarded.
 483       if (Sec->Name == "/DISCARD/") {
 484         discard(V);
 485         Sec->SectionCommands.clear();
 486         continue;
 487       }
 488
 489       // This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive
 490       // ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input
 491       // sections satisfy a given constraint. If not, a directive is handled
 492       // as if it wasn't present from the beginning.
 493       //
 494       // Because we'll iterate over SectionCommands many more times, the easy
 495       // way to "make it as if it wasn't present" is to make it empty.
 496       if (!matchConstraints(V, Sec->Constraint)) {
 497         for (InputSectionBase *S : V)
 498           S->Assigned = false;
 499         Sec->SectionCommands.clear();
 500         continue;
 501       }
 502
 503       // A directive may contain symbol definitions like this:
 504       // ".foo : { ...; bar = .; }". Handle them.
 505       for (BaseCommand *Base : Sec->SectionCommands)
 506         if (auto *OutCmd = dyn_cast<SymbolAssignment>(Base))
 507           addSymbol(OutCmd);
 508
 509       // Handle subalign (e.g. ".foo : SUBALIGN(32) { ... }"). If subalign
 510       // is given, input sections are aligned to that value, whether the
 511       // given value is larger or smaller than the original section alignment.
 512       if (Sec->SubalignExpr) {
 513         uint32_t Subalign = Sec->SubalignExpr().getValue();
 514         for (InputSectionBase *S : V)
 515           S->Alignment = Subalign;
 516       }
 517
 518       // Add input sections to an output section.
 519       for (InputSection *S : V)
 520         Sec->addSection(S);
 521
 522       Sec->SectionIndex = I++;
 523       if (Sec->Noload)
 524         Sec->Type = SHT_NOBITS;
 525       if (Sec->NonAlloc)
 526         Sec->Flags &= ~(uint64_t)SHF_ALLOC;
 527     }
 528   }
 529   Ctx = nullptr;
 530 }
 531
 532 static OutputSection *findByName(ArrayRef<BaseCommand *> Vec,
 533                                  StringRef Name) {
 534   for (BaseCommand *Base : Vec)
 535     if (auto *Sec = dyn_cast<OutputSection>(Base))
 536       if (Sec->Name == Name)
 537         return Sec;
 538   return nullptr;
 539 }
 540
 541 static OutputSection *createSection(InputSectionBase *IS,
 542                                     StringRef OutsecName) {
 543   OutputSection *Sec = Script->createOutputSection(OutsecName, "<internal>");
 544   Sec->addSection(cast<InputSection>(IS));
 545   return Sec;
 546 }
 547
 548 static OutputSection *addInputSec(StringMap<OutputSection *> &Map,
 549                                   InputSectionBase *IS, StringRef OutsecName) {
 550   // Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r
 551   // option is given. A section with SHT_GROUP defines a "section group", and
 552   // its members have SHF_GROUP attribute. Usually these flags have already been
 553   // stripped by InputFiles.cpp as section groups are processed and uniquified.
 554   // However, for the -r option, we want to pass through all section groups
 555   // as-is because adding/removing members or merging them with other groups
 556   // change their semantics.
 557   if (IS->Type == SHT_GROUP || (IS->Flags & SHF_GROUP))
 558     return createSection(IS, OutsecName);
 559
 560   // Imagine .zed : { *(.foo) *(.bar) } script. Both foo and bar may have
 561   // relocation sections .rela.foo and .rela.bar for example. Most tools do
 562   // not allow multiple REL[A] sections for output section. Hence we
 563   // should combine these relocation sections into single output.
 564   // We skip synthetic sections because it can be .rela.dyn/.rela.plt or any
 565   // other REL[A] sections created by linker itself.
 566   if (!isa<SyntheticSection>(IS) &&
 567       (IS->Type == SHT_REL || IS->Type == SHT_RELA)) {
 568     auto *Sec = cast<InputSection>(IS);
 569     OutputSection *Out = Sec->getRelocatedSection()->getOutputSection();
 570
 571     if (Out->RelocationSection) {
 572       Out->RelocationSection->addSection(Sec);
 573       return nullptr;
 574     }
 575
 576     Out->RelocationSection = createSection(IS, OutsecName);
 577     return Out->RelocationSection;
 578   }
 579
 580   // When control reaches here, mergeable sections have already been merged into
 581   // synthetic sections. For relocatable case we want to create one output
 582   // section per syntetic section so that they have a valid sh_entsize.
 583   if (Config->Relocatable && (IS->Flags & SHF_MERGE))
 584     return createSection(IS, OutsecName);
 585
 586   //  The ELF spec just says
 587   // ----------------------------------------------------------------
 588   // In the first phase, input sections that match in name, type and
 589   // attribute flags should be concatenated into single sections.
 590   // ----------------------------------------------------------------
 591   //
 592   // However, it is clear that at least some flags have to be ignored for
 593   // section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be
 594   // ignored. We should not have two output .text sections just because one was
 595   // in a group and another was not for example.
 596   //
 597   // It also seems that wording was a late addition and didn't get the
 598   // necessary scrutiny.
 599   //
 600   // Merging sections with different flags is expected by some users. One
 601   // reason is that if one file has
 602   //
 603   // int *const bar __attribute__((section(".foo"))) = (int *)0;
 604   //
 605   // gcc with -fPIC will produce a read only .foo section. But if another
 606   // file has
 607   //
 608   // int zed;
 609   // int *const bar __attribute__((section(".foo"))) = (int *)&zed;
 610   //
 611   // gcc with -fPIC will produce a read write section.
 612   //
 613   // Last but not least, when using linker script the merge rules are forced by
 614   // the script. Unfortunately, linker scripts are name based. This means that
 615   // expressions like *(.foo*) can refer to multiple input sections with
 616   // different flags. We cannot put them in different output sections or we
 617   // would produce wrong results for
 618   //
 619   // start = .; *(.foo.*) end = .; *(.bar)
 620   //
 621   // and a mapping of .foo1 and .bar1 to one section and .foo2 and .bar2 to
 622   // another. The problem is that there is no way to layout those output
 623   // sections such that the .foo sections are the only thing between the start
 624   // and end symbols.
 625   //
 626   // Given the above issues, we instead merge sections by name and error on
 627   // incompatible types and flags.
 628   OutputSection *&Sec = Map[OutsecName];
 629   if (Sec) {
 630     Sec->addSection(cast<InputSection>(IS));
 631     return nullptr;
 632   }
 633
 634   Sec = createSection(IS, OutsecName);
 635   return Sec;
 636 }
 637
 638 // Add sections that didn't match any sections command.
 639 void LinkerScript::addOrphanSections() {
 640   unsigned End = SectionCommands.size();
 641   StringMap<OutputSection *> Map;
 642   std::vector<OutputSection *> V;
 643
 644   auto Add = [&](InputSectionBase *S) {
 645     if (!S->Live || S->Parent)
 646       return;
 647
 648     StringRef Name = getOutputSectionName(S);
 649
 650     if (Config->OrphanHandling == OrphanHandlingPolicy::Error)
 651       error(toString(S) + " is being placed in '" + Name + "'");
 652     else if (Config->OrphanHandling == OrphanHandlingPolicy::Warn)
 653       warn(toString(S) + " is being placed in '" + Name + "'");
 654
 655     if (OutputSection *Sec =
 656             findByName(makeArrayRef(SectionCommands).slice(0, End), 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 *IS : InputSections) {
 671     if (auto *Sec = dyn_cast<InputSection>(IS))
 672       if (InputSectionBase *Rel = Sec->getRelocatedSection())
 673         if (auto *RelIS = dyn_cast_or_null<InputSectionBase>(Rel->Parent))
 674           Add(RelIS);
 675     Add(IS);
 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   uint64_t Before = advance(0, 1);
 704   uint64_t Pos = advance(S->getSize(), S->Alignment);
 705   S->OutSecOff = Pos - S->getSize() - Ctx->OutSec->Addr;
 706
 707   // Update output section size after adding each section. This is so that
 708   // SIZEOF works correctly in the case below:
 709   // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
 710   expandOutputSection(Pos - Before);
 711 }
 712
 713 void LinkerScript::switchTo(OutputSection *Sec) {
 714   Ctx->OutSec = Sec;
 715
 716   uint64_t Before = advance(0, 1);
 717   Ctx->OutSec->Addr = advance(0, Ctx->OutSec->Alignment);
 718   expandMemoryRegions(Ctx->OutSec->Addr - Before);
 719 }
 720
 721 // This function searches for a memory region to place the given output
 722 // section in. If found, a pointer to the appropriate memory region is
 723 // returned. Otherwise, a nullptr is returned.
 724 MemoryRegion *LinkerScript::findMemoryRegion(OutputSection *Sec) {
 725   // If a memory region name was specified in the output section command,
 726   // then try to find that region first.
 727   if (!Sec->MemoryRegionName.empty()) {
 728     if (MemoryRegion *M = MemoryRegions.lookup(Sec->MemoryRegionName))
 729       return M;
 730     error("memory region '" + Sec->MemoryRegionName + "' not declared");
 731     return nullptr;
 732   }
 733
 734   // If at least one memory region is defined, all sections must
 735   // belong to some memory region. Otherwise, we don't need to do
 736   // anything for memory regions.
 737   if (MemoryRegions.empty())
 738     return nullptr;
 739
 740   // See if a region can be found by matching section flags.
 741   for (auto &Pair : MemoryRegions) {
 742     MemoryRegion *M = Pair.second;
 743     if ((M->Flags & Sec->Flags) && (M->NegFlags & Sec->Flags) == 0)
 744       return M;
 745   }
 746
 747   // Otherwise, no suitable region was found.
 748   if (Sec->Flags & SHF_ALLOC)
 749     error("no memory region specified for section '" + Sec->Name + "'");
 750   return nullptr;
 751 }
 752
 753 // This function assigns offsets to input sections and an output section
 754 // for a single sections command (e.g. ".text { *(.text); }").
 755 void LinkerScript::assignOffsets(OutputSection *Sec) {
 756   if (!(Sec->Flags & SHF_ALLOC))
 757     Dot = 0;
 758   else if (Sec->AddrExpr)
 759     setDot(Sec->AddrExpr, Sec->Location, false);
 760
 761   Ctx->MemRegion = Sec->MemRegion;
 762   Ctx->LMARegion = Sec->LMARegion;
 763   if (Ctx->MemRegion)
 764     Dot = Ctx->MemRegion->CurPos;
 765
 766   switchTo(Sec);
 767
 768   if (Sec->LMAExpr)
 769     Ctx->LMAOffset = Sec->LMAExpr().getValue() - Dot;
 770
 771   if (MemoryRegion *MR = Sec->LMARegion)
 772     Ctx->LMAOffset = MR->CurPos - Dot;
 773
 774   // If neither AT nor AT> is specified for an allocatable section, the linker
 775   // will set the LMA such that the difference between VMA and LMA for the
 776   // section is the same as the preceding output section in the same region
 777   // https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html
 778   if (PhdrEntry *L = Ctx->OutSec->PtLoad)
 779     L->LMAOffset = Ctx->LMAOffset;
 780
 781   // We can call this method multiple times during the creation of
 782   // thunks and want to start over calculation each time.
 783   Sec->Size = 0;
 784
 785   // We visited SectionsCommands from processSectionCommands to
 786   // layout sections. Now, we visit SectionsCommands again to fix
 787   // section offsets.
 788   for (BaseCommand *Base : Sec->SectionCommands) {
 789     // This handles the assignments to symbol or to the dot.
 790     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
 791       Cmd->Addr = Dot;
 792       assignSymbol(Cmd, true);
 793       Cmd->Size = Dot - Cmd->Addr;
 794       continue;
 795     }
 796
 797     // Handle BYTE(), SHORT(), LONG(), or QUAD().
 798     if (auto *Cmd = dyn_cast<ByteCommand>(Base)) {
 799       Cmd->Offset = Dot - Ctx->OutSec->Addr;
 800       Dot += Cmd->Size;
 801       expandOutputSection(Cmd->Size);
 802       continue;
 803     }
 804
 805     // Handle a single input section description command.
 806     // It calculates and assigns the offsets for each section and also
 807     // updates the output section size.
 808     auto *Cmd = cast<InputSectionDescription>(Base);
 809     for (InputSection *Sec : Cmd->Sections) {
 810       // We tentatively added all synthetic sections at the beginning and
 811       // removed empty ones afterwards (because there is no way to know
 812       // whether they were going be empty or not other than actually running
 813       // linker scripts.) We need to ignore remains of empty sections.
 814       if (auto *S = dyn_cast<SyntheticSection>(Sec))
 815         if (S->empty())
 816           continue;
 817
 818       if (!Sec->Live)
 819         continue;
 820       assert(Ctx->OutSec == Sec->getParent());
 821       output(Sec);
 822     }
 823   }
 824 }
 825
 826 static bool isDiscardable(OutputSection &Sec) {
 827   // We do not remove empty sections that are explicitly
 828   // assigned to any segment.
 829   if (!Sec.Phdrs.empty())
 830     return false;
 831
 832   // We do not want to remove sections that reference symbols in address and
 833   // other expressions. We add script symbols as undefined, and want to ensure
 834   // all of them are defined in the output, hence have to keep them.
 835   if (Sec.ExpressionsUseSymbols)
 836     return false;
 837
 838   for (BaseCommand *Base : Sec.SectionCommands) {
 839     if (auto Cmd = dyn_cast<SymbolAssignment>(Base))
 840       // Don't create empty output sections just for unreferenced PROVIDE
 841       // symbols.
 842       if (Cmd->Name != "." && !Cmd->Sym)
 843         continue;
 844
 845     if (!isa<InputSectionDescription>(*Base))
 846       return false;
 847   }
 848   return true;
 849 }
 850
 851 void LinkerScript::adjustSectionsBeforeSorting() {
 852   // If the output section contains only symbol assignments, create a
 853   // corresponding output section. The issue is what to do with linker script
 854   // like ".foo : { symbol = 42; }". One option would be to convert it to
 855   // "symbol = 42;". That is, move the symbol out of the empty section
 856   // description. That seems to be what bfd does for this simple case. The
 857   // problem is that this is not completely general. bfd will give up and
 858   // create a dummy section too if there is a ". = . + 1" inside the section
 859   // for example.
 860   // Given that we want to create the section, we have to worry what impact
 861   // it will have on the link. For example, if we just create a section with
 862   // 0 for flags, it would change which PT_LOADs are created.
 863   // We could remember that particular section is dummy and ignore it in
 864   // other parts of the linker, but unfortunately there are quite a few places
 865   // that would need to change:
 866   //   * The program header creation.
 867   //   * The orphan section placement.
 868   //   * The address assignment.
 869   // The other option is to pick flags that minimize the impact the section
 870   // will have on the rest of the linker. That is why we copy the flags from
 871   // the previous sections. Only a few flags are needed to keep the impact low.
 872   uint64_t Flags = SHF_ALLOC;
 873
 874   for (BaseCommand *&Cmd : SectionCommands) {
 875     auto *Sec = dyn_cast<OutputSection>(Cmd);
 876     if (!Sec)
 877       continue;
 878
 879     // Handle align (e.g. ".foo : ALIGN(16) { ... }").
 880     if (Sec->AlignExpr)
 881       Sec->Alignment =
 882           std::max<uint32_t>(Sec->Alignment, Sec->AlignExpr().getValue());
 883
 884     // A live output section means that some input section was added to it. It
 885     // might have been removed (if it was empty synthetic section), but we at
 886     // least know the flags.
 887     if (Sec->Live)
 888       Flags = Sec->Flags;
 889
 890     // We do not want to keep any special flags for output section
 891     // in case it is empty.
 892     bool IsEmpty = getInputSections(Sec).empty();
 893     if (IsEmpty)
 894       Sec->Flags = Flags & (SHF_ALLOC | SHF_WRITE | SHF_EXECINSTR);
 895
 896     if (IsEmpty && isDiscardable(*Sec)) {
 897       Sec->Live = false;
 898       Cmd = nullptr;
 899     }
 900   }
 901
 902   // It is common practice to use very generic linker scripts. So for any
 903   // given run some of the output sections in the script will be empty.
 904   // We could create corresponding empty output sections, but that would
 905   // clutter the output.
 906   // We instead remove trivially empty sections. The bfd linker seems even
 907   // more aggressive at removing them.
 908   llvm::erase_if(SectionCommands, [&](BaseCommand *Base) { return !Base; });
 909 }
 910
 911 void LinkerScript::adjustSectionsAfterSorting() {
 912   // Try and find an appropriate memory region to assign offsets in.
 913   for (BaseCommand *Base : SectionCommands) {
 914     if (auto *Sec = dyn_cast<OutputSection>(Base)) {
 915       if (!Sec->LMARegionName.empty()) {
 916         if (MemoryRegion *M = MemoryRegions.lookup(Sec->LMARegionName))
 917           Sec->LMARegion = M;
 918         else
 919           error("memory region '" + Sec->LMARegionName + "' not declared");
 920       }
 921       Sec->MemRegion = findMemoryRegion(Sec);
 922     }
 923   }
 924
 925   // If output section command doesn't specify any segments,
 926   // and we haven't previously assigned any section to segment,
 927   // then we simply assign section to the very first load segment.
 928   // Below is an example of such linker script:
 929   // PHDRS { seg PT_LOAD; }
 930   // SECTIONS { .aaa : { *(.aaa) } }
 931   std::vector<StringRef> DefPhdrs;
 932   auto FirstPtLoad = llvm::find_if(PhdrsCommands, [](const PhdrsCommand &Cmd) {
 933     return Cmd.Type == PT_LOAD;
 934   });
 935   if (FirstPtLoad != PhdrsCommands.end())
 936     DefPhdrs.push_back(FirstPtLoad->Name);
 937
 938   // Walk the commands and propagate the program headers to commands that don't
 939   // explicitly specify them.
 940   for (BaseCommand *Base : SectionCommands) {
 941     auto *Sec = dyn_cast<OutputSection>(Base);
 942     if (!Sec)
 943       continue;
 944
 945     if (Sec->Phdrs.empty()) {
 946       // To match the bfd linker script behaviour, only propagate program
 947       // headers to sections that are allocated.
 948       if (Sec->Flags & SHF_ALLOC)
 949         Sec->Phdrs = DefPhdrs;
 950     } else {
 951       DefPhdrs = Sec->Phdrs;
 952     }
 953   }
 954 }
 955
 956 static OutputSection *findFirstSection(PhdrEntry *Load) {
 957   for (OutputSection *Sec : OutputSections)
 958     if (Sec->PtLoad == Load)
 959       return Sec;
 960   return nullptr;
 961 }
 962
 963 static uint64_t computeBase(uint64_t Min, bool AllocateHeaders) {
 964   // If there is no SECTIONS or if the linkerscript is explicit about program
 965   // headers, do our best to allocate them.
 966   if (!Script->HasSectionsCommand || AllocateHeaders)
 967     return 0;
 968   // Otherwise only allocate program headers if that would not add a page.
 969   return alignDown(Min, Config->MaxPageSize);
 970 }
 971
 972 // Try to find an address for the file and program headers output sections,
 973 // which were unconditionally added to the first PT_LOAD segment earlier.
 974 //
 975 // When using the default layout, we check if the headers fit below the first
 976 // allocated section. When using a linker script, we also check if the headers
 977 // are covered by the output section. This allows omitting the headers by not
 978 // leaving enough space for them in the linker script; this pattern is common
 979 // in embedded systems.
 980 //
 981 // If there isn't enough space for these sections, we'll remove them from the
 982 // PT_LOAD segment, and we'll also remove the PT_PHDR segment.
 983 void LinkerScript::allocateHeaders(std::vector<PhdrEntry *> &Phdrs) {
 984   uint64_t Min = std::numeric_limits<uint64_t>::max();
 985   for (OutputSection *Sec : OutputSections)
 986     if (Sec->Flags & SHF_ALLOC)
 987       Min = std::min<uint64_t>(Min, Sec->Addr);
 988
 989   auto It = llvm::find_if(
 990       Phdrs, [](const PhdrEntry *E) { return E->p_type == PT_LOAD; });
 991   if (It == Phdrs.end())
 992     return;
 993   PhdrEntry *FirstPTLoad = *It;
 994
 995   bool HasExplicitHeaders =
 996       llvm::any_of(PhdrsCommands, [](const PhdrsCommand &Cmd) {
 997         return Cmd.HasPhdrs || Cmd.HasFilehdr;
 998       });
 999   uint64_t HeaderSize = getHeaderSize();
1000   if (HeaderSize <= Min - computeBase(Min, HasExplicitHeaders)) {
1001     Min = alignDown(Min - HeaderSize, Config->MaxPageSize);
1002     Out::ElfHeader->Addr = Min;
1003     Out::ProgramHeaders->Addr = Min + Out::ElfHeader->Size;
1004     return;
1005   }
1006
1007   // Error if we were explicitly asked to allocate headers.
1008   if (HasExplicitHeaders)
1009     error("could not allocate headers");
1010
1011   Out::ElfHeader->PtLoad = nullptr;
1012   Out::ProgramHeaders->PtLoad = nullptr;
1013   FirstPTLoad->FirstSec = findFirstSection(FirstPTLoad);
1014
1015   llvm::erase_if(Phdrs,
1016                  [](const PhdrEntry *E) { return E->p_type == PT_PHDR; });
1017 }
1018
1019 LinkerScript::AddressState::AddressState() {
1020   for (auto &MRI : Script->MemoryRegions) {
1021     MemoryRegion *MR = MRI.second;
1022     MR->CurPos = MR->Origin;
1023   }
1024 }
1025
1026 static uint64_t getInitialDot() {
1027   // By default linker scripts use an initial value of 0 for '.',
1028   // but prefer -image-base if set.
1029   if (Script->HasSectionsCommand)
1030     return Config->ImageBase ? *Config->ImageBase : 0;
1031
1032   uint64_t StartAddr = UINT64_MAX;
1033   // The Sections with -T<section> have been sorted in order of ascending
1034   // address. We must lower StartAddr if the lowest -T<section address> as
1035   // calls to setDot() must be monotonically increasing.
1036   for (auto &KV : Config->SectionStartMap)
1037     StartAddr = std::min(StartAddr, KV.second);
1038   return std::min(StartAddr, Target->getImageBase() + elf::getHeaderSize());
1039 }
1040
1041 // Here we assign addresses as instructed by linker script SECTIONS
1042 // sub-commands. Doing that allows us to use final VA values, so here
1043 // we also handle rest commands like symbol assignments and ASSERTs.
1044 void LinkerScript::assignAddresses() {
1045   Dot = getInitialDot();
1046
1047   auto Deleter = make_unique<AddressState>();
1048   Ctx = Deleter.get();
1049   ErrorOnMissingSection = true;
1050   switchTo(Aether);
1051
1052   for (BaseCommand *Base : SectionCommands) {
1053     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
1054       Cmd->Addr = Dot;
1055       assignSymbol(Cmd, false);
1056       Cmd->Size = Dot - Cmd->Addr;
1057       continue;
1058     }
1059     assignOffsets(cast<OutputSection>(Base));
1060   }
1061   Ctx = nullptr;
1062 }
1063
1064 // Creates program headers as instructed by PHDRS linker script command.
1065 std::vector<PhdrEntry *> LinkerScript::createPhdrs() {
1066   std::vector<PhdrEntry *> Ret;
1067
1068   // Process PHDRS and FILEHDR keywords because they are not
1069   // real output sections and cannot be added in the following loop.
1070   for (const PhdrsCommand &Cmd : PhdrsCommands) {
1071     PhdrEntry *Phdr = make<PhdrEntry>(Cmd.Type, Cmd.Flags ? *Cmd.Flags : PF_R);
1072
1073     if (Cmd.HasFilehdr)
1074       Phdr->add(Out::ElfHeader);
1075     if (Cmd.HasPhdrs)
1076       Phdr->add(Out::ProgramHeaders);
1077
1078     if (Cmd.LMAExpr) {
1079       Phdr->p_paddr = Cmd.LMAExpr().getValue();
1080       Phdr->HasLMA = true;
1081     }
1082     Ret.push_back(Phdr);
1083   }
1084
1085   // Add output sections to program headers.
1086   for (OutputSection *Sec : OutputSections) {
1087     // Assign headers specified by linker script
1088     for (size_t Id : getPhdrIndices(Sec)) {
1089       Ret[Id]->add(Sec);
1090       if (!PhdrsCommands[Id].Flags.hasValue())
1091         Ret[Id]->p_flags |= Sec->getPhdrFlags();
1092     }
1093   }
1094   return Ret;
1095 }
1096
1097 // Returns true if we should emit an .interp section.
1098 //
1099 // We usually do. But if PHDRS commands are given, and
1100 // no PT_INTERP is there, there's no place to emit an
1101 // .interp, so we don't do that in that case.
1102 bool LinkerScript::needsInterpSection() {
1103   if (PhdrsCommands.empty())
1104     return true;
1105   for (PhdrsCommand &Cmd : PhdrsCommands)
1106     if (Cmd.Type == PT_INTERP)
1107       return true;
1108   return false;
1109 }
1110
1111 ExprValue LinkerScript::getSymbolValue(StringRef Name, const Twine &Loc) {
1112   if (Name == ".") {
1113     if (Ctx)
1114       return {Ctx->OutSec, false, Dot - Ctx->OutSec->Addr, Loc};
1115     error(Loc + ": unable to get location counter value");
1116     return 0;
1117   }
1118
1119   if (Symbol *Sym = Symtab->find(Name)) {
1120     if (auto *DS = dyn_cast<Defined>(Sym))
1121       return {DS->Section, false, DS->Value, Loc};
1122     if (isa<SharedSymbol>(Sym))
1123       if (!ErrorOnMissingSection)
1124         return {nullptr, false, 0, Loc};
1125   }
1126
1127   error(Loc + ": symbol not found: " + Name);
1128   return 0;
1129 }
1130
1131 // Returns the index of the segment named Name.
1132 static Optional<size_t> getPhdrIndex(ArrayRef<PhdrsCommand> Vec,
1133                                      StringRef Name) {
1134   for (size_t I = 0; I < Vec.size(); ++I)
1135     if (Vec[I].Name == Name)
1136       return I;
1137   return None;
1138 }
1139
1140 // Returns indices of ELF headers containing specific section. Each index is a
1141 // zero based number of ELF header listed within PHDRS {} script block.
1142 std::vector<size_t> LinkerScript::getPhdrIndices(OutputSection *Cmd) {
1143   std::vector<size_t> Ret;
1144
1145   for (StringRef S : Cmd->Phdrs) {
1146     if (Optional<size_t> Idx = getPhdrIndex(PhdrsCommands, S))
1147       Ret.push_back(*Idx);
1148     else if (S != "NONE")
1149       error(Cmd->Location + ": section header '" + S +
1150             "' is not listed in PHDRS");
1151   }
1152   return Ret;
1153 }