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 "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   // Only expand the LMARegion if it is different from MemRegion.
 120   if (Ctx->LMARegion && Ctx->MemRegion != Ctx->LMARegion)
 121     expandMemoryRegion(Ctx->LMARegion, Size, Ctx->LMARegion->Name,
 122                        Ctx->OutSec->Name);
 123 }
 124
 125 void LinkerScript::expandOutputSection(uint64_t Size) {
 126   Ctx->OutSec->Size += Size;
 127   expandMemoryRegions(Size);
 128 }
 129
 130 void LinkerScript::setDot(Expr E, const Twine &Loc, bool InSec) {
 131   uint64_t Val = E().getValue();
 132   if (Val < Dot && InSec)
 133     error(Loc + ": unable to move location counter backward for: " +
 134           Ctx->OutSec->Name);
 135
 136   // Update to location counter means update to section size.
 137   if (InSec)
 138     expandOutputSection(Val - Dot);
 139   else
 140     expandMemoryRegions(Val - Dot);
 141
 142   Dot = Val;
 143 }
 144
 145 // Used for handling linker symbol assignments, for both finalizing
 146 // their values and doing early declarations. Returns true if symbol
 147 // should be defined from linker script.
 148 static bool shouldDefineSym(SymbolAssignment *Cmd) {
 149   if (Cmd->Name == ".")
 150     return false;
 151
 152   if (!Cmd->Provide)
 153     return true;
 154
 155   // If a symbol was in PROVIDE(), we need to define it only
 156   // when it is a referenced undefined symbol.
 157   Symbol *B = Symtab->find(Cmd->Name);
 158   if (B && !B->isDefined())
 159     return true;
 160   return false;
 161 }
 162
 163 // This function is called from processSectionCommands,
 164 // while we are fixing the output section layout.
 165 void LinkerScript::addSymbol(SymbolAssignment *Cmd) {
 166   if (!shouldDefineSym(Cmd))
 167     return;
 168
 169   // Define a symbol.
 170   Symbol *Sym;
 171   uint8_t Visibility = Cmd->Hidden ? STV_HIDDEN : STV_DEFAULT;
 172   std::tie(Sym, std::ignore) = Symtab->insert(Cmd->Name, /*Type*/ 0, Visibility,
 173                                               /*CanOmitFromDynSym*/ false,
 174                                               /*File*/ nullptr);
 175   ExprValue Value = Cmd->Expression();
 176   SectionBase *Sec = Value.isAbsolute() ? nullptr : Value.Sec;
 177
 178   // When this function is called, section addresses have not been
 179   // fixed yet. So, we may or may not know the value of the RHS
 180   // expression.
 181   //
 182   // For example, if an expression is `x = 42`, we know x is always 42.
 183   // However, if an expression is `x = .`, there's no way to know its
 184   // value at the moment.
 185   //
 186   // We want to set symbol values early if we can. This allows us to
 187   // use symbols as variables in linker scripts. Doing so allows us to
 188   // write expressions like this: `alignment = 16; . = ALIGN(., alignment)`.
 189   uint64_t SymValue = Value.Sec ? 0 : Value.getValue();
 190
 191   replaceSymbol<Defined>(Sym, nullptr, Cmd->Name, STB_GLOBAL, Visibility,
 192                          STT_NOTYPE, SymValue, 0, Sec);
 193   Cmd->Sym = cast<Defined>(Sym);
 194 }
 195
 196 // This function is called from LinkerScript::declareSymbols.
 197 // It creates a placeholder symbol if needed.
 198 static void declareSymbol(SymbolAssignment *Cmd) {
 199   if (!shouldDefineSym(Cmd))
 200     return;
 201
 202   // We can't calculate final value right now.
 203   Symbol *Sym;
 204   uint8_t Visibility = Cmd->Hidden ? STV_HIDDEN : STV_DEFAULT;
 205   std::tie(Sym, std::ignore) = Symtab->insert(Cmd->Name, /*Type*/ 0, Visibility,
 206                                               /*CanOmitFromDynSym*/ false,
 207                                               /*File*/ nullptr);
 208   replaceSymbol<Defined>(Sym, nullptr, Cmd->Name, STB_GLOBAL, Visibility,
 209                          STT_NOTYPE, 0, 0, nullptr);
 210   Cmd->Sym = cast<Defined>(Sym);
 211   Cmd->Provide = false;
 212 }
 213
 214 // This method is used to handle INSERT AFTER statement. Here we rebuild
 215 // the list of script commands to mix sections inserted into.
 216 void LinkerScript::processInsertCommands() {
 217   std::vector<BaseCommand *> V;
 218   auto Insert = [&](std::vector<BaseCommand *> &From) {
 219     V.insert(V.end(), From.begin(), From.end());
 220     From.clear();
 221   };
 222
 223   for (BaseCommand *Base : SectionCommands) {
 224     if (auto *OS = dyn_cast<OutputSection>(Base)) {
 225       Insert(InsertBeforeCommands[OS->Name]);
 226       V.push_back(Base);
 227       Insert(InsertAfterCommands[OS->Name]);
 228       continue;
 229     }
 230     V.push_back(Base);
 231   }
 232
 233   for (auto &Cmds : {InsertBeforeCommands, InsertAfterCommands})
 234     for (const std::pair<StringRef, std::vector<BaseCommand *>> &P : Cmds)
 235       if (!P.second.empty())
 236         error("unable to INSERT AFTER/BEFORE " + P.first +
 237               ": section not defined");
 238
 239   SectionCommands = std::move(V);
 240 }
 241
 242 // Symbols defined in script should not be inlined by LTO. At the same time
 243 // we don't know their final values until late stages of link. Here we scan
 244 // over symbol assignment commands and create placeholder symbols if needed.
 245 void LinkerScript::declareSymbols() {
 246   assert(!Ctx);
 247   for (BaseCommand *Base : SectionCommands) {
 248     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
 249       declareSymbol(Cmd);
 250       continue;
 251     }
 252
 253     // If the output section directive has constraints,
 254     // we can't say for sure if it is going to be included or not.
 255     // Skip such sections for now. Improve the checks if we ever
 256     // need symbols from that sections to be declared early.
 257     auto *Sec = cast<OutputSection>(Base);
 258     if (Sec->Constraint != ConstraintKind::NoConstraint)
 259       continue;
 260     for (BaseCommand *Base2 : Sec->SectionCommands)
 261       if (auto *Cmd = dyn_cast<SymbolAssignment>(Base2))
 262         declareSymbol(Cmd);
 263   }
 264 }
 265
 266 // This function is called from assignAddresses, while we are
 267 // fixing the output section addresses. This function is supposed
 268 // to set the final value for a given symbol assignment.
 269 void LinkerScript::assignSymbol(SymbolAssignment *Cmd, bool InSec) {
 270   if (Cmd->Name == ".") {
 271     setDot(Cmd->Expression, Cmd->Location, InSec);
 272     return;
 273   }
 274
 275   if (!Cmd->Sym)
 276     return;
 277
 278   ExprValue V = Cmd->Expression();
 279   if (V.isAbsolute()) {
 280     Cmd->Sym->Section = nullptr;
 281     Cmd->Sym->Value = V.getValue();
 282   } else {
 283     Cmd->Sym->Section = V.Sec;
 284     Cmd->Sym->Value = V.getSectionOffset();
 285   }
 286 }
 287
 288 static std::string getFilename(InputFile *File) {
 289   if (!File)
 290     return "";
 291   if (File->ArchiveName.empty())
 292     return File->getName();
 293   return (File->ArchiveName + "(" + File->getName() + ")").str();
 294 }
 295
 296 bool LinkerScript::shouldKeep(InputSectionBase *S) {
 297   if (KeptSections.empty())
 298     return false;
 299   std::string Filename = getFilename(S->File);
 300   for (InputSectionDescription *ID : KeptSections)
 301     if (ID->FilePat.match(Filename))
 302       for (SectionPattern &P : ID->SectionPatterns)
 303         if (P.SectionPat.match(S->Name))
 304           return true;
 305   return false;
 306 }
 307
 308 // A helper function for the SORT() command.
 309 static std::function<bool(InputSectionBase *, InputSectionBase *)>
 310 getComparator(SortSectionPolicy K) {
 311   switch (K) {
 312   case SortSectionPolicy::Alignment:
 313     return [](InputSectionBase *A, InputSectionBase *B) {
 314       // ">" is not a mistake. Sections with larger alignments are placed
 315       // before sections with smaller alignments in order to reduce the
 316       // amount of padding necessary. This is compatible with GNU.
 317       return A->Alignment > B->Alignment;
 318     };
 319   case SortSectionPolicy::Name:
 320     return [](InputSectionBase *A, InputSectionBase *B) {
 321       return A->Name < B->Name;
 322     };
 323   case SortSectionPolicy::Priority:
 324     return [](InputSectionBase *A, InputSectionBase *B) {
 325       return getPriority(A->Name) < getPriority(B->Name);
 326     };
 327   default:
 328     llvm_unreachable("unknown sort policy");
 329   }
 330 }
 331
 332 // A helper function for the SORT() command.
 333 static bool matchConstraints(ArrayRef<InputSection *> Sections,
 334                              ConstraintKind Kind) {
 335   if (Kind == ConstraintKind::NoConstraint)
 336     return true;
 337
 338   bool IsRW = llvm::any_of(
 339       Sections, [](InputSection *Sec) { return Sec->Flags & SHF_WRITE; });
 340
 341   return (IsRW && Kind == ConstraintKind::ReadWrite) ||
 342          (!IsRW && Kind == ConstraintKind::ReadOnly);
 343 }
 344
 345 static void sortSections(MutableArrayRef<InputSection *> Vec,
 346                          SortSectionPolicy K) {
 347   if (K != SortSectionPolicy::Default && K != SortSectionPolicy::None)
 348     std::stable_sort(Vec.begin(), Vec.end(), getComparator(K));
 349 }
 350
 351 // Sort sections as instructed by SORT-family commands and --sort-section
 352 // option. Because SORT-family commands can be nested at most two depth
 353 // (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
 354 // line option is respected even if a SORT command is given, the exact
 355 // behavior we have here is a bit complicated. Here are the rules.
 356 //
 357 // 1. If two SORT commands are given, --sort-section is ignored.
 358 // 2. If one SORT command is given, and if it is not SORT_NONE,
 359 //    --sort-section is handled as an inner SORT command.
 360 // 3. If one SORT command is given, and if it is SORT_NONE, don't sort.
 361 // 4. If no SORT command is given, sort according to --sort-section.
 362 static void sortInputSections(MutableArrayRef<InputSection *> Vec,
 363                               const SectionPattern &Pat) {
 364   if (Pat.SortOuter == SortSectionPolicy::None)
 365     return;
 366
 367   if (Pat.SortInner == SortSectionPolicy::Default)
 368     sortSections(Vec, Config->SortSection);
 369   else
 370     sortSections(Vec, Pat.SortInner);
 371   sortSections(Vec, Pat.SortOuter);
 372 }
 373
 374 // Compute and remember which sections the InputSectionDescription matches.
 375 std::vector<InputSection *>
 376 LinkerScript::computeInputSections(const InputSectionDescription *Cmd) {
 377   std::vector<InputSection *> Ret;
 378
 379   // Collects all sections that satisfy constraints of Cmd.
 380   for (const SectionPattern &Pat : Cmd->SectionPatterns) {
 381     size_t SizeBefore = Ret.size();
 382
 383     for (InputSectionBase *Sec : InputSections) {
 384       if (!Sec->Live || Sec->Assigned)
 385         continue;
 386
 387       // For -emit-relocs we have to ignore entries like
 388       //   .rela.dyn : { *(.rela.data) }
 389       // which are common because they are in the default bfd script.
 390       // We do not ignore SHT_REL[A] linker-synthesized sections here because
 391       // want to support scripts that do custom layout for them.
 392       if (auto *IS = dyn_cast<InputSection>(Sec))
 393         if (IS->getRelocatedSection())
 394           continue;
 395
 396       std::string Filename = getFilename(Sec->File);
 397       if (!Cmd->FilePat.match(Filename) ||
 398           Pat.ExcludedFilePat.match(Filename) ||
 399           !Pat.SectionPat.match(Sec->Name))
 400         continue;
 401
 402       // It is safe to assume that Sec is an InputSection
 403       // because mergeable or EH input sections have already been
 404       // handled and eliminated.
 405       Ret.push_back(cast<InputSection>(Sec));
 406       Sec->Assigned = true;
 407     }
 408
 409     sortInputSections(MutableArrayRef<InputSection *>(Ret).slice(SizeBefore),
 410                       Pat);
 411   }
 412   return Ret;
 413 }
 414
 415 void LinkerScript::discard(ArrayRef<InputSection *> V) {
 416   for (InputSection *S : V) {
 417     if (S == InX::ShStrTab || S == InX::Dynamic || S == InX::DynSymTab ||
 418         S == InX::DynStrTab || S == InX::RelaPlt || S == InX::RelaDyn ||
 419         S == InX::RelrDyn)
 420       error("discarding " + S->Name + " section is not allowed");
 421
 422     // You can discard .hash and .gnu.hash sections by linker scripts. Since
 423     // they are synthesized sections, we need to handle them differently than
 424     // other regular sections.
 425     if (S == InX::GnuHashTab)
 426       InX::GnuHashTab = nullptr;
 427     if (S == InX::HashTab)
 428       InX::HashTab = nullptr;
 429
 430     S->Assigned = false;
 431     S->Live = false;
 432     discard(S->DependentSections);
 433   }
 434 }
 435
 436 std::vector<InputSection *>
 437 LinkerScript::createInputSectionList(OutputSection &OutCmd) {
 438   std::vector<InputSection *> Ret;
 439
 440   for (BaseCommand *Base : OutCmd.SectionCommands) {
 441     if (auto *Cmd = dyn_cast<InputSectionDescription>(Base)) {
 442       Cmd->Sections = computeInputSections(Cmd);
 443       Ret.insert(Ret.end(), Cmd->Sections.begin(), Cmd->Sections.end());
 444     }
 445   }
 446   return Ret;
 447 }
 448
 449 void LinkerScript::processSectionCommands() {
 450   // A symbol can be assigned before any section is mentioned in the linker
 451   // script. In an DSO, the symbol values are addresses, so the only important
 452   // section values are:
 453   // * SHN_UNDEF
 454   // * SHN_ABS
 455   // * Any value meaning a regular section.
 456   // To handle that, create a dummy aether section that fills the void before
 457   // the linker scripts switches to another section. It has an index of one
 458   // which will map to whatever the first actual section is.
 459   Aether = make<OutputSection>("", 0, SHF_ALLOC);
 460   Aether->SectionIndex = 1;
 461
 462   // Ctx captures the local AddressState and makes it accessible deliberately.
 463   // This is needed as there are some cases where we cannot just
 464   // thread the current state through to a lambda function created by the
 465   // script parser.
 466   auto Deleter = make_unique<AddressState>();
 467   Ctx = Deleter.get();
 468   Ctx->OutSec = Aether;
 469
 470   size_t I = 0;
 471   // Add input sections to output sections.
 472   for (BaseCommand *Base : SectionCommands) {
 473     // Handle symbol assignments outside of any output section.
 474     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
 475       addSymbol(Cmd);
 476       continue;
 477     }
 478
 479     if (auto *Sec = dyn_cast<OutputSection>(Base)) {
 480       std::vector<InputSection *> V = createInputSectionList(*Sec);
 481
 482       // The output section name `/DISCARD/' is special.
 483       // Any input section assigned to it is discarded.
 484       if (Sec->Name == "/DISCARD/") {
 485         discard(V);
 486         Sec->SectionCommands.clear();
 487         continue;
 488       }
 489
 490       // This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive
 491       // ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input
 492       // sections satisfy a given constraint. If not, a directive is handled
 493       // as if it wasn't present from the beginning.
 494       //
 495       // Because we'll iterate over SectionCommands many more times, the easy
 496       // way to "make it as if it wasn't present" is to make it empty.
 497       if (!matchConstraints(V, Sec->Constraint)) {
 498         for (InputSectionBase *S : V)
 499           S->Assigned = false;
 500         Sec->SectionCommands.clear();
 501         continue;
 502       }
 503
 504       // A directive may contain symbol definitions like this:
 505       // ".foo : { ...; bar = .; }". Handle them.
 506       for (BaseCommand *Base : Sec->SectionCommands)
 507         if (auto *OutCmd = dyn_cast<SymbolAssignment>(Base))
 508           addSymbol(OutCmd);
 509
 510       // Handle subalign (e.g. ".foo : SUBALIGN(32) { ... }"). If subalign
 511       // is given, input sections are aligned to that value, whether the
 512       // given value is larger or smaller than the original section alignment.
 513       if (Sec->SubalignExpr) {
 514         uint32_t Subalign = Sec->SubalignExpr().getValue();
 515         for (InputSectionBase *S : V)
 516           S->Alignment = Subalign;
 517       }
 518
 519       // Add input sections to an output section.
 520       for (InputSection *S : V)
 521         Sec->addSection(S);
 522
 523       Sec->SectionIndex = I++;
 524       if (Sec->Noload)
 525         Sec->Type = SHT_NOBITS;
 526       if (Sec->NonAlloc)
 527         Sec->Flags &= ~(uint64_t)SHF_ALLOC;
 528     }
 529   }
 530   Ctx = nullptr;
 531 }
 532
 533 static OutputSection *findByName(ArrayRef<BaseCommand *> Vec,
 534                                  StringRef Name) {
 535   for (BaseCommand *Base : Vec)
 536     if (auto *Sec = dyn_cast<OutputSection>(Base))
 537       if (Sec->Name == Name)
 538         return Sec;
 539   return nullptr;
 540 }
 541
 542 static OutputSection *createSection(InputSectionBase *IS,
 543                                     StringRef OutsecName) {
 544   OutputSection *Sec = Script->createOutputSection(OutsecName, "<internal>");
 545   Sec->addSection(cast<InputSection>(IS));
 546   return Sec;
 547 }
 548
 549 static OutputSection *addInputSec(StringMap<OutputSection *> &Map,
 550                                   InputSectionBase *IS, StringRef OutsecName) {
 551   // Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r
 552   // option is given. A section with SHT_GROUP defines a "section group", and
 553   // its members have SHF_GROUP attribute. Usually these flags have already been
 554   // stripped by InputFiles.cpp as section groups are processed and uniquified.
 555   // However, for the -r option, we want to pass through all section groups
 556   // as-is because adding/removing members or merging them with other groups
 557   // change their semantics.
 558   if (IS->Type == SHT_GROUP || (IS->Flags & SHF_GROUP))
 559     return createSection(IS, OutsecName);
 560
 561   // Imagine .zed : { *(.foo) *(.bar) } script. Both foo and bar may have
 562   // relocation sections .rela.foo and .rela.bar for example. Most tools do
 563   // not allow multiple REL[A] sections for output section. Hence we
 564   // should combine these relocation sections into single output.
 565   // We skip synthetic sections because it can be .rela.dyn/.rela.plt or any
 566   // other REL[A] sections created by linker itself.
 567   if (!isa<SyntheticSection>(IS) &&
 568       (IS->Type == SHT_REL || IS->Type == SHT_RELA)) {
 569     auto *Sec = cast<InputSection>(IS);
 570     OutputSection *Out = Sec->getRelocatedSection()->getOutputSection();
 571
 572     if (Out->RelocationSection) {
 573       Out->RelocationSection->addSection(Sec);
 574       return nullptr;
 575     }
 576
 577     Out->RelocationSection = createSection(IS, OutsecName);
 578     return Out->RelocationSection;
 579   }
 580
 581   // When control reaches here, mergeable sections have already been merged into
 582   // synthetic sections. For relocatable case we want to create one output
 583   // section per syntetic section so that they have a valid sh_entsize.
 584   if (Config->Relocatable && (IS->Flags & SHF_MERGE))
 585     return createSection(IS, OutsecName);
 586
 587   //  The ELF spec just says
 588   // ----------------------------------------------------------------
 589   // In the first phase, input sections that match in name, type and
 590   // attribute flags should be concatenated into single sections.
 591   // ----------------------------------------------------------------
 592   //
 593   // However, it is clear that at least some flags have to be ignored for
 594   // section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be
 595   // ignored. We should not have two output .text sections just because one was
 596   // in a group and another was not for example.
 597   //
 598   // It also seems that wording was a late addition and didn't get the
 599   // necessary scrutiny.
 600   //
 601   // Merging sections with different flags is expected by some users. One
 602   // reason is that if one file has
 603   //
 604   // int *const bar __attribute__((section(".foo"))) = (int *)0;
 605   //
 606   // gcc with -fPIC will produce a read only .foo section. But if another
 607   // file has
 608   //
 609   // int zed;
 610   // int *const bar __attribute__((section(".foo"))) = (int *)&zed;
 611   //
 612   // gcc with -fPIC will produce a read write section.
 613   //
 614   // Last but not least, when using linker script the merge rules are forced by
 615   // the script. Unfortunately, linker scripts are name based. This means that
 616   // expressions like *(.foo*) can refer to multiple input sections with
 617   // different flags. We cannot put them in different output sections or we
 618   // would produce wrong results for
 619   //
 620   // start = .; *(.foo.*) end = .; *(.bar)
 621   //
 622   // and a mapping of .foo1 and .bar1 to one section and .foo2 and .bar2 to
 623   // another. The problem is that there is no way to layout those output
 624   // sections such that the .foo sections are the only thing between the start
 625   // and end symbols.
 626   //
 627   // Given the above issues, we instead merge sections by name and error on
 628   // incompatible types and flags.
 629   OutputSection *&Sec = Map[OutsecName];
 630   if (Sec) {
 631     Sec->addSection(cast<InputSection>(IS));
 632     return nullptr;
 633   }
 634
 635   Sec = createSection(IS, OutsecName);
 636   return Sec;
 637 }
 638
 639 // Add sections that didn't match any sections command.
 640 void LinkerScript::addOrphanSections() {
 641   unsigned End = SectionCommands.size();
 642   StringMap<OutputSection *> Map;
 643   std::vector<OutputSection *> V;
 644
 645   auto Add = [&](InputSectionBase *S) {
 646     if (!S->Live || 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 =
 657             findByName(makeArrayRef(SectionCommands).slice(0, End), Name)) {
 658       Sec->addSection(cast<InputSection>(S));
 659       return;
 660     }
 661
 662     if (OutputSection *OS = addInputSec(Map, S, Name))
 663       V.push_back(OS);
 664     assert(S->getOutputSection()->SectionIndex == UINT32_MAX);
 665   };
 666
 667   // For futher --emit-reloc handling code we need target output section
 668   // to be created before we create relocation output section, so we want
 669   // to create target sections first. We do not want priority handling
 670   // for synthetic sections because them are special.
 671   for (InputSectionBase *IS : InputSections) {
 672     if (auto *Sec = dyn_cast<InputSection>(IS))
 673       if (InputSectionBase *Rel = Sec->getRelocatedSection())
 674         if (auto *RelIS = dyn_cast_or_null<InputSectionBase>(Rel->Parent))
 675           Add(RelIS);
 676     Add(IS);
 677   }
 678
 679   // If no SECTIONS command was given, we should insert sections commands
 680   // before others, so that we can handle scripts which refers them,
 681   // for example: "foo = ABSOLUTE(ADDR(.text)));".
 682   // When SECTIONS command is present we just add all orphans to the end.
 683   if (HasSectionsCommand)
 684     SectionCommands.insert(SectionCommands.end(), V.begin(), V.end());
 685   else
 686     SectionCommands.insert(SectionCommands.begin(), V.begin(), V.end());
 687 }
 688
 689 uint64_t LinkerScript::advance(uint64_t Size, unsigned Alignment) {
 690   bool IsTbss =
 691       (Ctx->OutSec->Flags & SHF_TLS) && Ctx->OutSec->Type == SHT_NOBITS;
 692   uint64_t Start = IsTbss ? Dot + Ctx->ThreadBssOffset : Dot;
 693   Start = alignTo(Start, Alignment);
 694   uint64_t End = Start + Size;
 695
 696   if (IsTbss)
 697     Ctx->ThreadBssOffset = End - Dot;
 698   else
 699     Dot = End;
 700   return End;
 701 }
 702
 703 void LinkerScript::output(InputSection *S) {
 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   else if (Sec->AddrExpr)
 767     setDot(Sec->AddrExpr, Sec->Location, false);
 768
 769   Ctx->MemRegion = Sec->MemRegion;
 770   Ctx->LMARegion = Sec->LMARegion;
 771   if (Ctx->MemRegion)
 772     Dot = Ctx->MemRegion->CurPos;
 773
 774   switchTo(Sec);
 775
 776   if (Sec->LMAExpr)
 777     Ctx->LMAOffset = Sec->LMAExpr().getValue() - Dot;
 778
 779   if (MemoryRegion *MR = Sec->LMARegion)
 780     Ctx->LMAOffset = MR->CurPos - Dot;
 781
 782   // If neither AT nor AT> is specified for an allocatable section, the linker
 783   // will set the LMA such that the difference between VMA and LMA for the
 784   // section is the same as the preceding output section in the same region
 785   // https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html
 786   // This, however, should only be done by the first "non-header" section
 787   // in the segment.
 788   if (PhdrEntry *L = Ctx->OutSec->PtLoad)
 789     if (Sec == findFirstSection(L))
 790       L->LMAOffset = Ctx->LMAOffset;
 791
 792   // We can call this method multiple times during the creation of
 793   // thunks and want to start over calculation each time.
 794   Sec->Size = 0;
 795
 796   // We visited SectionsCommands from processSectionCommands to
 797   // layout sections. Now, we visit SectionsCommands again to fix
 798   // section offsets.
 799   for (BaseCommand *Base : Sec->SectionCommands) {
 800     // This handles the assignments to symbol or to the dot.
 801     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
 802       Cmd->Addr = Dot;
 803       assignSymbol(Cmd, true);
 804       Cmd->Size = Dot - Cmd->Addr;
 805       continue;
 806     }
 807
 808     // Handle BYTE(), SHORT(), LONG(), or QUAD().
 809     if (auto *Cmd = dyn_cast<ByteCommand>(Base)) {
 810       Cmd->Offset = Dot - Ctx->OutSec->Addr;
 811       Dot += Cmd->Size;
 812       expandOutputSection(Cmd->Size);
 813       continue;
 814     }
 815
 816     // Handle a single input section description command.
 817     // It calculates and assigns the offsets for each section and also
 818     // updates the output section size.
 819     auto *Cmd = cast<InputSectionDescription>(Base);
 820     for (InputSection *Sec : Cmd->Sections) {
 821       // We tentatively added all synthetic sections at the beginning and
 822       // removed empty ones afterwards (because there is no way to know
 823       // whether they were going be empty or not other than actually running
 824       // linker scripts.) We need to ignore remains of empty sections.
 825       if (auto *S = dyn_cast<SyntheticSection>(Sec))
 826         if (S->empty())
 827           continue;
 828
 829       if (!Sec->Live)
 830         continue;
 831       assert(Ctx->OutSec == Sec->getParent());
 832       output(Sec);
 833     }
 834   }
 835 }
 836
 837 static bool isDiscardable(OutputSection &Sec) {
 838   // We do not remove empty sections that are explicitly
 839   // assigned to any segment.
 840   if (!Sec.Phdrs.empty())
 841     return false;
 842
 843   // We do not want to remove sections that reference symbols in address and
 844   // other expressions. We add script symbols as undefined, and want to ensure
 845   // all of them are defined in the output, hence have to keep them.
 846   if (Sec.ExpressionsUseSymbols)
 847     return false;
 848
 849   for (BaseCommand *Base : Sec.SectionCommands) {
 850     if (auto Cmd = dyn_cast<SymbolAssignment>(Base))
 851       // Don't create empty output sections just for unreferenced PROVIDE
 852       // symbols.
 853       if (Cmd->Name != "." && !Cmd->Sym)
 854         continue;
 855
 856     if (!isa<InputSectionDescription>(*Base))
 857       return false;
 858   }
 859   return true;
 860 }
 861
 862 void LinkerScript::adjustSectionsBeforeSorting() {
 863   // If the output section contains only symbol assignments, create a
 864   // corresponding output section. The issue is what to do with linker script
 865   // like ".foo : { symbol = 42; }". One option would be to convert it to
 866   // "symbol = 42;". That is, move the symbol out of the empty section
 867   // description. That seems to be what bfd does for this simple case. The
 868   // problem is that this is not completely general. bfd will give up and
 869   // create a dummy section too if there is a ". = . + 1" inside the section
 870   // for example.
 871   // Given that we want to create the section, we have to worry what impact
 872   // it will have on the link. For example, if we just create a section with
 873   // 0 for flags, it would change which PT_LOADs are created.
 874   // We could remember that particular section is dummy and ignore it in
 875   // other parts of the linker, but unfortunately there are quite a few places
 876   // that would need to change:
 877   //   * The program header creation.
 878   //   * The orphan section placement.
 879   //   * The address assignment.
 880   // The other option is to pick flags that minimize the impact the section
 881   // will have on the rest of the linker. That is why we copy the flags from
 882   // the previous sections. Only a few flags are needed to keep the impact low.
 883   uint64_t Flags = SHF_ALLOC;
 884
 885   for (BaseCommand *&Cmd : SectionCommands) {
 886     auto *Sec = dyn_cast<OutputSection>(Cmd);
 887     if (!Sec)
 888       continue;
 889
 890     // Handle align (e.g. ".foo : ALIGN(16) { ... }").
 891     if (Sec->AlignExpr)
 892       Sec->Alignment =
 893           std::max<uint32_t>(Sec->Alignment, Sec->AlignExpr().getValue());
 894
 895     // A live output section means that some input section was added to it. It
 896     // might have been removed (if it was empty synthetic section), but we at
 897     // least know the flags.
 898     if (Sec->Live)
 899       Flags = Sec->Flags;
 900
 901     // We do not want to keep any special flags for output section
 902     // in case it is empty.
 903     bool IsEmpty = getInputSections(Sec).empty();
 904     if (IsEmpty)
 905       Sec->Flags = Flags & (SHF_ALLOC | SHF_WRITE | SHF_EXECINSTR);
 906
 907     if (IsEmpty && isDiscardable(*Sec)) {
 908       Sec->Live = false;
 909       Cmd = nullptr;
 910     }
 911   }
 912
 913   // It is common practice to use very generic linker scripts. So for any
 914   // given run some of the output sections in the script will be empty.
 915   // We could create corresponding empty output sections, but that would
 916   // clutter the output.
 917   // We instead remove trivially empty sections. The bfd linker seems even
 918   // more aggressive at removing them.
 919   llvm::erase_if(SectionCommands, [&](BaseCommand *Base) { return !Base; });
 920 }
 921
 922 void LinkerScript::adjustSectionsAfterSorting() {
 923   // Try and find an appropriate memory region to assign offsets in.
 924   for (BaseCommand *Base : SectionCommands) {
 925     if (auto *Sec = dyn_cast<OutputSection>(Base)) {
 926       if (!Sec->LMARegionName.empty()) {
 927         if (MemoryRegion *M = MemoryRegions.lookup(Sec->LMARegionName))
 928           Sec->LMARegion = M;
 929         else
 930           error("memory region '" + Sec->LMARegionName + "' not declared");
 931       }
 932       Sec->MemRegion = findMemoryRegion(Sec);
 933     }
 934   }
 935
 936   // If output section command doesn't specify any segments,
 937   // and we haven't previously assigned any section to segment,
 938   // then we simply assign section to the very first load segment.
 939   // Below is an example of such linker script:
 940   // PHDRS { seg PT_LOAD; }
 941   // SECTIONS { .aaa : { *(.aaa) } }
 942   std::vector<StringRef> DefPhdrs;
 943   auto FirstPtLoad = llvm::find_if(PhdrsCommands, [](const PhdrsCommand &Cmd) {
 944     return Cmd.Type == PT_LOAD;
 945   });
 946   if (FirstPtLoad != PhdrsCommands.end())
 947     DefPhdrs.push_back(FirstPtLoad->Name);
 948
 949   // Walk the commands and propagate the program headers to commands that don't
 950   // explicitly specify them.
 951   for (BaseCommand *Base : SectionCommands) {
 952     auto *Sec = dyn_cast<OutputSection>(Base);
 953     if (!Sec)
 954       continue;
 955
 956     if (Sec->Phdrs.empty()) {
 957       // To match the bfd linker script behaviour, only propagate program
 958       // headers to sections that are allocated.
 959       if (Sec->Flags & SHF_ALLOC)
 960         Sec->Phdrs = DefPhdrs;
 961     } else {
 962       DefPhdrs = Sec->Phdrs;
 963     }
 964   }
 965 }
 966
 967 static uint64_t computeBase(uint64_t Min, bool AllocateHeaders) {
 968   // If there is no SECTIONS or if the linkerscript is explicit about program
 969   // headers, do our best to allocate them.
 970   if (!Script->HasSectionsCommand || AllocateHeaders)
 971     return 0;
 972   // Otherwise only allocate program headers if that would not add a page.
 973   return alignDown(Min, Config->MaxPageSize);
 974 }
 975
 976 // Try to find an address for the file and program headers output sections,
 977 // which were unconditionally added to the first PT_LOAD segment earlier.
 978 //
 979 // When using the default layout, we check if the headers fit below the first
 980 // allocated section. When using a linker script, we also check if the headers
 981 // are covered by the output section. This allows omitting the headers by not
 982 // leaving enough space for them in the linker script; this pattern is common
 983 // in embedded systems.
 984 //
 985 // If there isn't enough space for these sections, we'll remove them from the
 986 // PT_LOAD segment, and we'll also remove the PT_PHDR segment.
 987 void LinkerScript::allocateHeaders(std::vector<PhdrEntry *> &Phdrs) {
 988   uint64_t Min = std::numeric_limits<uint64_t>::max();
 989   for (OutputSection *Sec : OutputSections)
 990     if (Sec->Flags & SHF_ALLOC)
 991       Min = std::min<uint64_t>(Min, Sec->Addr);
 992
 993   auto It = llvm::find_if(
 994       Phdrs, [](const PhdrEntry *E) { return E->p_type == PT_LOAD; });
 995   if (It == Phdrs.end())
 996     return;
 997   PhdrEntry *FirstPTLoad = *It;
 998
 999   bool HasExplicitHeaders =
1000       llvm::any_of(PhdrsCommands, [](const PhdrsCommand &Cmd) {
1001         return Cmd.HasPhdrs || Cmd.HasFilehdr;
1002       });
1003   uint64_t HeaderSize = getHeaderSize();
1004   if (HeaderSize <= Min - computeBase(Min, HasExplicitHeaders)) {
1005     Min = alignDown(Min - HeaderSize, Config->MaxPageSize);
1006     Out::ElfHeader->Addr = Min;
1007     Out::ProgramHeaders->Addr = Min + Out::ElfHeader->Size;
1008     return;
1009   }
1010
1011   // Error if we were explicitly asked to allocate headers.
1012   if (HasExplicitHeaders)
1013     error("could not allocate headers");
1014
1015   Out::ElfHeader->PtLoad = nullptr;
1016   Out::ProgramHeaders->PtLoad = nullptr;
1017   FirstPTLoad->FirstSec = findFirstSection(FirstPTLoad);
1018
1019   llvm::erase_if(Phdrs,
1020                  [](const PhdrEntry *E) { return E->p_type == PT_PHDR; });
1021 }
1022
1023 LinkerScript::AddressState::AddressState() {
1024   for (auto &MRI : Script->MemoryRegions) {
1025     MemoryRegion *MR = MRI.second;
1026     MR->CurPos = MR->Origin;
1027   }
1028 }
1029
1030 static uint64_t getInitialDot() {
1031   // By default linker scripts use an initial value of 0 for '.',
1032   // but prefer -image-base if set.
1033   if (Script->HasSectionsCommand)
1034     return Config->ImageBase ? *Config->ImageBase : 0;
1035
1036   uint64_t StartAddr = UINT64_MAX;
1037   // The Sections with -T<section> have been sorted in order of ascending
1038   // address. We must lower StartAddr if the lowest -T<section address> as
1039   // calls to setDot() must be monotonically increasing.
1040   for (auto &KV : Config->SectionStartMap)
1041     StartAddr = std::min(StartAddr, KV.second);
1042   return std::min(StartAddr, Target->getImageBase() + elf::getHeaderSize());
1043 }
1044
1045 // Here we assign addresses as instructed by linker script SECTIONS
1046 // sub-commands. Doing that allows us to use final VA values, so here
1047 // we also handle rest commands like symbol assignments and ASSERTs.
1048 void LinkerScript::assignAddresses() {
1049   Dot = getInitialDot();
1050
1051   auto Deleter = make_unique<AddressState>();
1052   Ctx = Deleter.get();
1053   ErrorOnMissingSection = true;
1054   switchTo(Aether);
1055
1056   for (BaseCommand *Base : SectionCommands) {
1057     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
1058       Cmd->Addr = Dot;
1059       assignSymbol(Cmd, false);
1060       Cmd->Size = Dot - Cmd->Addr;
1061       continue;
1062     }
1063     assignOffsets(cast<OutputSection>(Base));
1064   }
1065   Ctx = nullptr;
1066 }
1067
1068 // Creates program headers as instructed by PHDRS linker script command.
1069 std::vector<PhdrEntry *> LinkerScript::createPhdrs() {
1070   std::vector<PhdrEntry *> Ret;
1071
1072   // Process PHDRS and FILEHDR keywords because they are not
1073   // real output sections and cannot be added in the following loop.
1074   for (const PhdrsCommand &Cmd : PhdrsCommands) {
1075     PhdrEntry *Phdr = make<PhdrEntry>(Cmd.Type, Cmd.Flags ? *Cmd.Flags : PF_R);
1076
1077     if (Cmd.HasFilehdr)
1078       Phdr->add(Out::ElfHeader);
1079     if (Cmd.HasPhdrs)
1080       Phdr->add(Out::ProgramHeaders);
1081
1082     if (Cmd.LMAExpr) {
1083       Phdr->p_paddr = Cmd.LMAExpr().getValue();
1084       Phdr->HasLMA = true;
1085     }
1086     Ret.push_back(Phdr);
1087   }
1088
1089   // Add output sections to program headers.
1090   for (OutputSection *Sec : OutputSections) {
1091     // Assign headers specified by linker script
1092     for (size_t Id : getPhdrIndices(Sec)) {
1093       Ret[Id]->add(Sec);
1094       if (!PhdrsCommands[Id].Flags.hasValue())
1095         Ret[Id]->p_flags |= Sec->getPhdrFlags();
1096     }
1097   }
1098   return Ret;
1099 }
1100
1101 // Returns true if we should emit an .interp section.
1102 //
1103 // We usually do. But if PHDRS commands are given, and
1104 // no PT_INTERP is there, there's no place to emit an
1105 // .interp, so we don't do that in that case.
1106 bool LinkerScript::needsInterpSection() {
1107   if (PhdrsCommands.empty())
1108     return true;
1109   for (PhdrsCommand &Cmd : PhdrsCommands)
1110     if (Cmd.Type == PT_INTERP)
1111       return true;
1112   return false;
1113 }
1114
1115 ExprValue LinkerScript::getSymbolValue(StringRef Name, const Twine &Loc) {
1116   if (Name == ".") {
1117     if (Ctx)
1118       return {Ctx->OutSec, false, Dot - Ctx->OutSec->Addr, Loc};
1119     error(Loc + ": unable to get location counter value");
1120     return 0;
1121   }
1122
1123   if (Symbol *Sym = Symtab->find(Name)) {
1124     if (auto *DS = dyn_cast<Defined>(Sym))
1125       return {DS->Section, false, DS->Value, Loc};
1126     if (isa<SharedSymbol>(Sym))
1127       if (!ErrorOnMissingSection)
1128         return {nullptr, false, 0, Loc};
1129   }
1130
1131   error(Loc + ": symbol not found: " + Name);
1132   return 0;
1133 }
1134
1135 // Returns the index of the segment named Name.
1136 static Optional<size_t> getPhdrIndex(ArrayRef<PhdrsCommand> Vec,
1137                                      StringRef Name) {
1138   for (size_t I = 0; I < Vec.size(); ++I)
1139     if (Vec[I].Name == Name)
1140       return I;
1141   return None;
1142 }
1143
1144 // Returns indices of ELF headers containing specific section. Each index is a
1145 // zero based number of ELF header listed within PHDRS {} script block.
1146 std::vector<size_t> LinkerScript::getPhdrIndices(OutputSection *Cmd) {
1147   std::vector<size_t> Ret;
1148
1149   for (StringRef S : Cmd->Phdrs) {
1150     if (Optional<size_t> Idx = getPhdrIndex(PhdrsCommands, S))
1151       Ret.push_back(*Idx);
1152     else if (S != "NONE")
1153       error(Cmd->Location + ": section header '" + S +
1154             "' is not listed in PHDRS");
1155   }
1156   return Ret;
1157 }