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 "Memory.h"
  18 #include "OutputSections.h"
  19 #include "Strings.h"
  20 #include "SymbolTable.h"
  21 #include "Symbols.h"
  22 #include "SyntheticSections.h"
  23 #include "Writer.h"
  24 #include "llvm/ADT/STLExtras.h"
  25 #include "llvm/ADT/StringRef.h"
  26 #include "llvm/Support/Casting.h"
  27 #include "llvm/Support/ELF.h"
  28 #include "llvm/Support/Endian.h"
  29 #include "llvm/Support/ErrorHandling.h"
  30 #include "llvm/Support/FileSystem.h"
  31 #include "llvm/Support/Path.h"
  32 #include <algorithm>
  33 #include <cassert>
  34 #include <cstddef>
  35 #include <cstdint>
  36 #include <iterator>
  37 #include <limits>
  38 #include <string>
  39 #include <vector>
  40
  41 using namespace llvm;
  42 using namespace llvm::ELF;
  43 using namespace llvm::object;
  44 using namespace llvm::support::endian;
  45 using namespace lld;
  46 using namespace lld::elf;
  47
  48 LinkerScript *elf::Script;
  49
  50 uint64_t ExprValue::getValue() const {
  51   if (Sec)
  52     return Sec->getOffset(Val) + Sec->getOutputSection()->Addr;
  53   return Val;
  54 }
  55
  56 uint64_t ExprValue::getSecAddr() const {
  57   if (Sec)
  58     return Sec->getOffset(0) + Sec->getOutputSection()->Addr;
  59   return 0;
  60 }
  61
  62 template <class ELFT> static SymbolBody *addRegular(SymbolAssignment *Cmd) {
  63   Symbol *Sym;
  64   uint8_t Visibility = Cmd->Hidden ? STV_HIDDEN : STV_DEFAULT;
  65   std::tie(Sym, std::ignore) = Symtab<ELFT>::X->insert(
  66       Cmd->Name, /*Type*/ 0, Visibility, /*CanOmitFromDynSym*/ false,
  67       /*File*/ nullptr);
  68   Sym->Binding = STB_GLOBAL;
  69   ExprValue Value = Cmd->Expression();
  70   SectionBase *Sec = Value.isAbsolute() ? nullptr : Value.Sec;
  71
  72   // We want to set symbol values early if we can. This allows us to use symbols
  73   // as variables in linker scripts. Doing so allows us to write expressions
  74   // like this: `alignment = 16; . = ALIGN(., alignment)`
  75   uint64_t SymValue = Value.isAbsolute() ? Value.getValue() : 0;
  76   replaceBody<DefinedRegular>(Sym, Cmd->Name, /*IsLocal=*/false, Visibility,
  77                               STT_NOTYPE, SymValue, 0, Sec, nullptr);
  78   return Sym->body();
  79 }
  80
  81 OutputSection *LinkerScript::getOutputSection(const Twine &Loc,
  82                                               StringRef Name) {
  83   for (OutputSection *Sec : *OutputSections)
  84     if (Sec->Name == Name)
  85       return Sec;
  86
  87   static OutputSection Dummy("", 0, 0);
  88   if (ErrorOnMissingSection)
  89     error(Loc + ": undefined section " + Name);
  90   return &Dummy;
  91 }
  92
  93 // This function is essentially the same as getOutputSection(Name)->Size,
  94 // but it won't print out an error message if a given section is not found.
  95 //
  96 // Linker script does not create an output section if its content is empty.
  97 // We want to allow SIZEOF(.foo) where .foo is a section which happened to
  98 // be empty. That is why this function is different from getOutputSection().
  99 uint64_t LinkerScript::getOutputSectionSize(StringRef Name) {
 100   for (OutputSection *Sec : *OutputSections)
 101     if (Sec->Name == Name)
 102       return Sec->Size;
 103   return 0;
 104 }
 105
 106 void LinkerScript::setDot(Expr E, const Twine &Loc, bool InSec) {
 107   uint64_t Val = E().getValue();
 108   if (Val < Dot) {
 109     if (InSec)
 110       error(Loc + ": unable to move location counter backward for: " +
 111             CurOutSec->Name);
 112     else
 113       error(Loc + ": unable to move location counter backward");
 114   }
 115   Dot = Val;
 116   // Update to location counter means update to section size.
 117   if (InSec)
 118     CurOutSec->Size = Dot - CurOutSec->Addr;
 119 }
 120
 121 // Sets value of a symbol. Two kinds of symbols are processed: synthetic
 122 // symbols, whose value is an offset from beginning of section and regular
 123 // symbols whose value is absolute.
 124 void LinkerScript::assignSymbol(SymbolAssignment *Cmd, bool InSec) {
 125   if (Cmd->Name == ".") {
 126     setDot(Cmd->Expression, Cmd->Location, InSec);
 127     return;
 128   }
 129
 130   if (!Cmd->Sym)
 131     return;
 132
 133   auto *Sym = cast<DefinedRegular>(Cmd->Sym);
 134   ExprValue V = Cmd->Expression();
 135   if (V.isAbsolute()) {
 136     Sym->Value = V.getValue();
 137   } else {
 138     Sym->Section = V.Sec;
 139     if (Sym->Section->Flags & SHF_ALLOC)
 140       Sym->Value = V.Val;
 141     else
 142       Sym->Value = V.getValue();
 143   }
 144 }
 145
 146 static SymbolBody *findSymbol(StringRef S) {
 147   switch (Config->EKind) {
 148   case ELF32LEKind:
 149     return Symtab<ELF32LE>::X->find(S);
 150   case ELF32BEKind:
 151     return Symtab<ELF32BE>::X->find(S);
 152   case ELF64LEKind:
 153     return Symtab<ELF64LE>::X->find(S);
 154   case ELF64BEKind:
 155     return Symtab<ELF64BE>::X->find(S);
 156   default:
 157     llvm_unreachable("unknown Config->EKind");
 158   }
 159 }
 160
 161 static SymbolBody *addRegularSymbol(SymbolAssignment *Cmd) {
 162   switch (Config->EKind) {
 163   case ELF32LEKind:
 164     return addRegular<ELF32LE>(Cmd);
 165   case ELF32BEKind:
 166     return addRegular<ELF32BE>(Cmd);
 167   case ELF64LEKind:
 168     return addRegular<ELF64LE>(Cmd);
 169   case ELF64BEKind:
 170     return addRegular<ELF64BE>(Cmd);
 171   default:
 172     llvm_unreachable("unknown Config->EKind");
 173   }
 174 }
 175
 176 void LinkerScript::addSymbol(SymbolAssignment *Cmd) {
 177   if (Cmd->Name == ".")
 178     return;
 179
 180   // If a symbol was in PROVIDE(), we need to define it only when
 181   // it is a referenced undefined symbol.
 182   SymbolBody *B = findSymbol(Cmd->Name);
 183   if (Cmd->Provide && (!B || B->isDefined()))
 184     return;
 185
 186   Cmd->Sym = addRegularSymbol(Cmd);
 187 }
 188
 189 bool SymbolAssignment::classof(const BaseCommand *C) {
 190   return C->Kind == AssignmentKind;
 191 }
 192
 193 bool OutputSectionCommand::classof(const BaseCommand *C) {
 194   return C->Kind == OutputSectionKind;
 195 }
 196
 197 bool InputSectionDescription::classof(const BaseCommand *C) {
 198   return C->Kind == InputSectionKind;
 199 }
 200
 201 bool AssertCommand::classof(const BaseCommand *C) {
 202   return C->Kind == AssertKind;
 203 }
 204
 205 bool BytesDataCommand::classof(const BaseCommand *C) {
 206   return C->Kind == BytesDataKind;
 207 }
 208
 209 static StringRef basename(InputSectionBase *S) {
 210   if (S->File)
 211     return sys::path::filename(S->File->getName());
 212   return "";
 213 }
 214
 215 bool LinkerScript::shouldKeep(InputSectionBase *S) {
 216   for (InputSectionDescription *ID : Opt.KeptSections)
 217     if (ID->FilePat.match(basename(S)))
 218       for (SectionPattern &P : ID->SectionPatterns)
 219         if (P.SectionPat.match(S->Name))
 220           return true;
 221   return false;
 222 }
 223
 224 // A helper function for the SORT() command.
 225 static std::function<bool(InputSectionBase *, InputSectionBase *)>
 226 getComparator(SortSectionPolicy K) {
 227   switch (K) {
 228   case SortSectionPolicy::Alignment:
 229     return [](InputSectionBase *A, InputSectionBase *B) {
 230       // ">" is not a mistake. Sections with larger alignments are placed
 231       // before sections with smaller alignments in order to reduce the
 232       // amount of padding necessary. This is compatible with GNU.
 233       return A->Alignment > B->Alignment;
 234     };
 235   case SortSectionPolicy::Name:
 236     return [](InputSectionBase *A, InputSectionBase *B) {
 237       return A->Name < B->Name;
 238     };
 239   case SortSectionPolicy::Priority:
 240     return [](InputSectionBase *A, InputSectionBase *B) {
 241       return getPriority(A->Name) < getPriority(B->Name);
 242     };
 243   default:
 244     llvm_unreachable("unknown sort policy");
 245   }
 246 }
 247
 248 // A helper function for the SORT() command.
 249 static bool matchConstraints(ArrayRef<InputSectionBase *> Sections,
 250                              ConstraintKind Kind) {
 251   if (Kind == ConstraintKind::NoConstraint)
 252     return true;
 253
 254   bool IsRW = llvm::any_of(Sections, [](InputSectionBase *Sec) {
 255     return static_cast<InputSectionBase *>(Sec)->Flags & SHF_WRITE;
 256   });
 257
 258   return (IsRW && Kind == ConstraintKind::ReadWrite) ||
 259          (!IsRW && Kind == ConstraintKind::ReadOnly);
 260 }
 261
 262 static void sortSections(InputSectionBase **Begin, InputSectionBase **End,
 263                          SortSectionPolicy K) {
 264   if (K != SortSectionPolicy::Default && K != SortSectionPolicy::None)
 265     std::stable_sort(Begin, End, getComparator(K));
 266 }
 267
 268 // Compute and remember which sections the InputSectionDescription matches.
 269 std::vector<InputSectionBase *>
 270 LinkerScript::computeInputSections(const InputSectionDescription *Cmd) {
 271   std::vector<InputSectionBase *> Ret;
 272
 273   // Collects all sections that satisfy constraints of Cmd.
 274   for (const SectionPattern &Pat : Cmd->SectionPatterns) {
 275     size_t SizeBefore = Ret.size();
 276
 277     for (InputSectionBase *Sec : InputSections) {
 278       if (Sec->Assigned)
 279         continue;
 280
 281       // For -emit-relocs we have to ignore entries like
 282       //   .rela.dyn : { *(.rela.data) }
 283       // which are common because they are in the default bfd script.
 284       if (Sec->Type == SHT_REL || Sec->Type == SHT_RELA)
 285         continue;
 286
 287       StringRef Filename = basename(Sec);
 288       if (!Cmd->FilePat.match(Filename) ||
 289           Pat.ExcludedFilePat.match(Filename) ||
 290           !Pat.SectionPat.match(Sec->Name))
 291         continue;
 292
 293       Ret.push_back(Sec);
 294       Sec->Assigned = true;
 295     }
 296
 297     // Sort sections as instructed by SORT-family commands and --sort-section
 298     // option. Because SORT-family commands can be nested at most two depth
 299     // (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command
 300     // line option is respected even if a SORT command is given, the exact
 301     // behavior we have here is a bit complicated. Here are the rules.
 302     //
 303     // 1. If two SORT commands are given, --sort-section is ignored.
 304     // 2. If one SORT command is given, and if it is not SORT_NONE,
 305     //    --sort-section is handled as an inner SORT command.
 306     // 3. If one SORT command is given, and if it is SORT_NONE, don't sort.
 307     // 4. If no SORT command is given, sort according to --sort-section.
 308     InputSectionBase **Begin = Ret.data() + SizeBefore;
 309     InputSectionBase **End = Ret.data() + Ret.size();
 310     if (Pat.SortOuter != SortSectionPolicy::None) {
 311       if (Pat.SortInner == SortSectionPolicy::Default)
 312         sortSections(Begin, End, Config->SortSection);
 313       else
 314         sortSections(Begin, End, Pat.SortInner);
 315       sortSections(Begin, End, Pat.SortOuter);
 316     }
 317   }
 318   return Ret;
 319 }
 320
 321 void LinkerScript::discard(ArrayRef<InputSectionBase *> V) {
 322   for (InputSectionBase *S : V) {
 323     S->Live = false;
 324     if (S == InX::ShStrTab)
 325       error("discarding .shstrtab section is not allowed");
 326     discard(S->DependentSections);
 327   }
 328 }
 329
 330 std::vector<InputSectionBase *>
 331 LinkerScript::createInputSectionList(OutputSectionCommand &OutCmd) {
 332   std::vector<InputSectionBase *> Ret;
 333
 334   for (BaseCommand *Base : OutCmd.Commands) {
 335     auto *Cmd = dyn_cast<InputSectionDescription>(Base);
 336     if (!Cmd)
 337       continue;
 338
 339     Cmd->Sections = computeInputSections(Cmd);
 340     Ret.insert(Ret.end(), Cmd->Sections.begin(), Cmd->Sections.end());
 341   }
 342
 343   return Ret;
 344 }
 345
 346 void LinkerScript::processCommands(OutputSectionFactory &Factory) {
 347   // A symbol can be assigned before any section is mentioned in the linker
 348   // script. In an DSO, the symbol values are addresses, so the only important
 349   // section values are:
 350   // * SHN_UNDEF
 351   // * SHN_ABS
 352   // * Any value meaning a regular section.
 353   // To handle that, create a dummy aether section that fills the void before
 354   // the linker scripts switches to another section. It has an index of one
 355   // which will map to whatever the first actual section is.
 356   Aether = make<OutputSection>("", 0, SHF_ALLOC);
 357   Aether->SectionIndex = 1;
 358   CurOutSec = Aether;
 359   Dot = 0;
 360
 361   for (size_t I = 0; I < Opt.Commands.size(); ++I) {
 362     // Handle symbol assignments outside of any output section.
 363     if (auto *Cmd = dyn_cast<SymbolAssignment>(Opt.Commands[I])) {
 364       addSymbol(Cmd);
 365       continue;
 366     }
 367
 368     if (auto *Cmd = dyn_cast<OutputSectionCommand>(Opt.Commands[I])) {
 369       std::vector<InputSectionBase *> V = createInputSectionList(*Cmd);
 370
 371       // The output section name `/DISCARD/' is special.
 372       // Any input section assigned to it is discarded.
 373       if (Cmd->Name == "/DISCARD/") {
 374         discard(V);
 375         continue;
 376       }
 377
 378       // This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive
 379       // ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input
 380       // sections satisfy a given constraint. If not, a directive is handled
 381       // as if it wasn't present from the beginning.
 382       //
 383       // Because we'll iterate over Commands many more times, the easiest
 384       // way to "make it as if it wasn't present" is to just remove it.
 385       if (!matchConstraints(V, Cmd->Constraint)) {
 386         for (InputSectionBase *S : V)
 387           S->Assigned = false;
 388         Opt.Commands.erase(Opt.Commands.begin() + I);
 389         --I;
 390         continue;
 391       }
 392
 393       // A directive may contain symbol definitions like this:
 394       // ".foo : { ...; bar = .; }". Handle them.
 395       for (BaseCommand *Base : Cmd->Commands)
 396         if (auto *OutCmd = dyn_cast<SymbolAssignment>(Base))
 397           addSymbol(OutCmd);
 398
 399       // Handle subalign (e.g. ".foo : SUBALIGN(32) { ... }"). If subalign
 400       // is given, input sections are aligned to that value, whether the
 401       // given value is larger or smaller than the original section alignment.
 402       if (Cmd->SubalignExpr) {
 403         uint32_t Subalign = Cmd->SubalignExpr().getValue();
 404         for (InputSectionBase *S : V)
 405           S->Alignment = Subalign;
 406       }
 407
 408       // Add input sections to an output section.
 409       unsigned Pos = 0;
 410       for (InputSectionBase *S : V) {
 411         // The actual offset will be computed during
 412         // assignAddresses. For now, use the index as a very crude
 413         // approximation so that it is at least easy for other code to
 414         // know the section order.
 415         cast<InputSection>(S)->OutSecOff = Pos++;
 416         Factory.addInputSec(S, Cmd->Name, Cmd->Sec);
 417       }
 418     }
 419   }
 420   CurOutSec = nullptr;
 421 }
 422
 423 void LinkerScript::fabricateDefaultCommands(bool AllocateHeader) {
 424   std::vector<BaseCommand *> Commands;
 425
 426   // Define start address
 427   uint64_t StartAddr = Config->ImageBase;
 428   if (AllocateHeader)
 429     StartAddr += elf::getHeaderSize();
 430
 431   // The Sections with -T<section> have been sorted in order of ascending
 432   // address. We must lower StartAddr if the lowest -T<section address> as
 433   // calls to setDot() must be monotonically increasing.
 434   for (auto& KV : Config->SectionStartMap)
 435     StartAddr = std::min(StartAddr, KV.second);
 436
 437   Commands.push_back(
 438       make<SymbolAssignment>(".", [=] { return StartAddr; }, ""));
 439
 440   // For each OutputSection that needs a VA fabricate an OutputSectionCommand
 441   // with an InputSectionDescription describing the InputSections
 442   for (OutputSection *Sec : *OutputSections) {
 443     if (!(Sec->Flags & SHF_ALLOC))
 444       continue;
 445
 446     auto *OSCmd = make<OutputSectionCommand>(Sec->Name);
 447     OSCmd->Sec = Sec;
 448
 449     // Prefer user supplied address over additional alignment constraint
 450     auto I = Config->SectionStartMap.find(Sec->Name);
 451     if (I != Config->SectionStartMap.end())
 452       Commands.push_back(
 453           make<SymbolAssignment>(".", [=] { return I->second; }, ""));
 454     else if (Sec->PageAlign)
 455       OSCmd->AddrExpr = [=] {
 456         return alignTo(Script->getDot(), Config->MaxPageSize);
 457       };
 458
 459     Commands.push_back(OSCmd);
 460     if (Sec->Sections.size()) {
 461       auto *ISD = make<InputSectionDescription>("");
 462       OSCmd->Commands.push_back(ISD);
 463       for (InputSection *ISec : Sec->Sections) {
 464         ISD->Sections.push_back(ISec);
 465         ISec->Assigned = true;
 466       }
 467     }
 468   }
 469   // SECTIONS commands run before other non SECTIONS commands
 470   Commands.insert(Commands.end(), Opt.Commands.begin(), Opt.Commands.end());
 471   Opt.Commands = std::move(Commands);
 472 }
 473
 474 // Add sections that didn't match any sections command.
 475 void LinkerScript::addOrphanSections(OutputSectionFactory &Factory) {
 476   for (InputSectionBase *S : InputSections) {
 477     if (!S->Live || S->OutSec)
 478       continue;
 479     StringRef Name = getOutputSectionName(S->Name);
 480     auto I = std::find_if(
 481         Opt.Commands.begin(), Opt.Commands.end(), [&](BaseCommand *Base) {
 482           if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
 483             return Cmd->Name == Name;
 484           return false;
 485         });
 486     if (I == Opt.Commands.end()) {
 487       Factory.addInputSec(S, Name);
 488     } else {
 489       auto *Cmd = cast<OutputSectionCommand>(*I);
 490       Factory.addInputSec(S, Name, Cmd->Sec);
 491       auto *ISD = make<InputSectionDescription>("");
 492       ISD->Sections.push_back(S);
 493       Cmd->Commands.push_back(ISD);
 494     }
 495   }
 496 }
 497
 498 static bool isTbss(OutputSection *Sec) {
 499   return (Sec->Flags & SHF_TLS) && Sec->Type == SHT_NOBITS;
 500 }
 501
 502 void LinkerScript::output(InputSection *S) {
 503   bool IsTbss = isTbss(CurOutSec);
 504
 505   uint64_t Pos = IsTbss ? Dot + ThreadBssOffset : Dot;
 506   Pos = alignTo(Pos, S->Alignment);
 507   S->OutSecOff = Pos - CurOutSec->Addr;
 508   Pos += S->getSize();
 509
 510   // Update output section size after adding each section. This is so that
 511   // SIZEOF works correctly in the case below:
 512   // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
 513   CurOutSec->Size = Pos - CurOutSec->Addr;
 514
 515   // If there is a memory region associated with this input section, then
 516   // place the section in that region and update the region index.
 517   if (CurMemRegion) {
 518     CurMemRegion->Offset += CurOutSec->Size;
 519     uint64_t CurSize = CurMemRegion->Offset - CurMemRegion->Origin;
 520     if (CurSize > CurMemRegion->Length) {
 521       uint64_t OverflowAmt = CurSize - CurMemRegion->Length;
 522       error("section '" + CurOutSec->Name + "' will not fit in region '" +
 523             CurMemRegion->Name + "': overflowed by " + Twine(OverflowAmt) +
 524             " bytes");
 525     }
 526   }
 527
 528   if (IsTbss)
 529     ThreadBssOffset = Pos - Dot;
 530   else
 531     Dot = Pos;
 532 }
 533
 534 void LinkerScript::switchTo(OutputSection *Sec) {
 535   if (CurOutSec == Sec)
 536     return;
 537
 538   CurOutSec = Sec;
 539
 540   Dot = alignTo(Dot, CurOutSec->Alignment);
 541   CurOutSec->Addr = isTbss(CurOutSec) ? Dot + ThreadBssOffset : Dot;
 542
 543   // If neither AT nor AT> is specified for an allocatable section, the linker
 544   // will set the LMA such that the difference between VMA and LMA for the
 545   // section is the same as the preceding output section in the same region
 546   // https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html
 547   if (LMAOffset)
 548     CurOutSec->LMAOffset = LMAOffset();
 549 }
 550
 551 void LinkerScript::process(BaseCommand &Base) {
 552   // This handles the assignments to symbol or to the dot.
 553   if (auto *Cmd = dyn_cast<SymbolAssignment>(&Base)) {
 554     assignSymbol(Cmd, true);
 555     return;
 556   }
 557
 558   // Handle BYTE(), SHORT(), LONG(), or QUAD().
 559   if (auto *Cmd = dyn_cast<BytesDataCommand>(&Base)) {
 560     Cmd->Offset = Dot - CurOutSec->Addr;
 561     Dot += Cmd->Size;
 562     CurOutSec->Size = Dot - CurOutSec->Addr;
 563     return;
 564   }
 565
 566   // Handle ASSERT().
 567   if (auto *Cmd = dyn_cast<AssertCommand>(&Base)) {
 568     Cmd->Expression();
 569     return;
 570   }
 571
 572   // Handle a single input section description command.
 573   // It calculates and assigns the offsets for each section and also
 574   // updates the output section size.
 575   auto &Cmd = cast<InputSectionDescription>(Base);
 576   for (InputSectionBase *Sec : Cmd.Sections) {
 577     // We tentatively added all synthetic sections at the beginning and removed
 578     // empty ones afterwards (because there is no way to know whether they were
 579     // going be empty or not other than actually running linker scripts.)
 580     // We need to ignore remains of empty sections.
 581     if (auto *S = dyn_cast<SyntheticSection>(Sec))
 582       if (S->empty())
 583         continue;
 584
 585     if (!Sec->Live)
 586       continue;
 587     assert(CurOutSec == Sec->OutSec);
 588     output(cast<InputSection>(Sec));
 589   }
 590 }
 591
 592 // This function searches for a memory region to place the given output
 593 // section in. If found, a pointer to the appropriate memory region is
 594 // returned. Otherwise, a nullptr is returned.
 595 MemoryRegion *LinkerScript::findMemoryRegion(OutputSectionCommand *Cmd) {
 596   // If a memory region name was specified in the output section command,
 597   // then try to find that region first.
 598   if (!Cmd->MemoryRegionName.empty()) {
 599     auto It = Opt.MemoryRegions.find(Cmd->MemoryRegionName);
 600     if (It != Opt.MemoryRegions.end())
 601       return &It->second;
 602     error("memory region '" + Cmd->MemoryRegionName + "' not declared");
 603     return nullptr;
 604   }
 605
 606   // If at least one memory region is defined, all sections must
 607   // belong to some memory region. Otherwise, we don't need to do
 608   // anything for memory regions.
 609   if (Opt.MemoryRegions.empty())
 610     return nullptr;
 611
 612   OutputSection *Sec = Cmd->Sec;
 613   // See if a region can be found by matching section flags.
 614   for (auto &Pair : Opt.MemoryRegions) {
 615     MemoryRegion &M = Pair.second;
 616     if ((M.Flags & Sec->Flags) && (M.NegFlags & Sec->Flags) == 0)
 617       return &M;
 618   }
 619
 620   // Otherwise, no suitable region was found.
 621   if (Sec->Flags & SHF_ALLOC)
 622     error("no memory region specified for section '" + Sec->Name + "'");
 623   return nullptr;
 624 }
 625
 626 // This function assigns offsets to input sections and an output section
 627 // for a single sections command (e.g. ".text { *(.text); }").
 628 void LinkerScript::assignOffsets(OutputSectionCommand *Cmd) {
 629   OutputSection *Sec = Cmd->Sec;
 630   if (!Sec)
 631     return;
 632
 633   if (Cmd->AddrExpr && (Sec->Flags & SHF_ALLOC))
 634     setDot(Cmd->AddrExpr, Cmd->Location, false);
 635
 636   if (Cmd->LMAExpr) {
 637     uint64_t D = Dot;
 638     LMAOffset = [=] { return Cmd->LMAExpr().getValue() - D; };
 639   }
 640
 641   CurMemRegion = Cmd->MemRegion;
 642   if (CurMemRegion)
 643     Dot = CurMemRegion->Offset;
 644   switchTo(Sec);
 645
 646   for (BaseCommand *C : Cmd->Commands)
 647     process(*C);
 648 }
 649
 650 void LinkerScript::removeEmptyCommands() {
 651   // It is common practice to use very generic linker scripts. So for any
 652   // given run some of the output sections in the script will be empty.
 653   // We could create corresponding empty output sections, but that would
 654   // clutter the output.
 655   // We instead remove trivially empty sections. The bfd linker seems even
 656   // more aggressive at removing them.
 657   auto Pos = std::remove_if(
 658       Opt.Commands.begin(), Opt.Commands.end(), [&](BaseCommand *Base) {
 659         if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
 660           return std::find(OutputSections->begin(), OutputSections->end(),
 661                            Cmd->Sec) == OutputSections->end();
 662         return false;
 663       });
 664   Opt.Commands.erase(Pos, Opt.Commands.end());
 665 }
 666
 667 static bool isAllSectionDescription(const OutputSectionCommand &Cmd) {
 668   for (BaseCommand *Base : Cmd.Commands)
 669     if (!isa<InputSectionDescription>(*Base))
 670       return false;
 671   return true;
 672 }
 673
 674 void LinkerScript::adjustSectionsBeforeSorting() {
 675   // If the output section contains only symbol assignments, create a
 676   // corresponding output section. The bfd linker seems to only create them if
 677   // '.' is assigned to, but creating these section should not have any bad
 678   // consequeces and gives us a section to put the symbol in.
 679   uint64_t Flags = SHF_ALLOC;
 680   uint32_t Type = SHT_PROGBITS;
 681   for (BaseCommand *Base : Opt.Commands) {
 682     auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
 683     if (!Cmd)
 684       continue;
 685     if (OutputSection *Sec = Cmd->Sec) {
 686       Flags = Sec->Flags;
 687       Type = Sec->Type;
 688       continue;
 689     }
 690
 691     if (isAllSectionDescription(*Cmd))
 692       continue;
 693
 694     auto *OutSec = make<OutputSection>(Cmd->Name, Type, Flags);
 695     OutputSections->push_back(OutSec);
 696     Cmd->Sec = OutSec;
 697   }
 698 }
 699
 700 void LinkerScript::adjustSectionsAfterSorting() {
 701   placeOrphanSections();
 702
 703   // Try and find an appropriate memory region to assign offsets in.
 704   for (BaseCommand *Base : Opt.Commands) {
 705     if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base)) {
 706       Cmd->MemRegion = findMemoryRegion(Cmd);
 707       // Handle align (e.g. ".foo : ALIGN(16) { ... }").
 708       if (Cmd->AlignExpr)
 709         Cmd->Sec->updateAlignment(Cmd->AlignExpr().getValue());
 710     }
 711   }
 712
 713   // If output section command doesn't specify any segments,
 714   // and we haven't previously assigned any section to segment,
 715   // then we simply assign section to the very first load segment.
 716   // Below is an example of such linker script:
 717   // PHDRS { seg PT_LOAD; }
 718   // SECTIONS { .aaa : { *(.aaa) } }
 719   std::vector<StringRef> DefPhdrs;
 720   auto FirstPtLoad =
 721       std::find_if(Opt.PhdrsCommands.begin(), Opt.PhdrsCommands.end(),
 722                    [](const PhdrsCommand &Cmd) { return Cmd.Type == PT_LOAD; });
 723   if (FirstPtLoad != Opt.PhdrsCommands.end())
 724     DefPhdrs.push_back(FirstPtLoad->Name);
 725
 726   // Walk the commands and propagate the program headers to commands that don't
 727   // explicitly specify them.
 728   for (BaseCommand *Base : Opt.Commands) {
 729     auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
 730     if (!Cmd)
 731       continue;
 732
 733     if (Cmd->Phdrs.empty())
 734       Cmd->Phdrs = DefPhdrs;
 735     else
 736       DefPhdrs = Cmd->Phdrs;
 737   }
 738
 739   removeEmptyCommands();
 740 }
 741
 742 // When placing orphan sections, we want to place them after symbol assignments
 743 // so that an orphan after
 744 //   begin_foo = .;
 745 //   foo : { *(foo) }
 746 //   end_foo = .;
 747 // doesn't break the intended meaning of the begin/end symbols.
 748 // We don't want to go over sections since Writer<ELFT>::sortSections is the
 749 // one in charge of deciding the order of the sections.
 750 // We don't want to go over alignments, since doing so in
 751 //  rx_sec : { *(rx_sec) }
 752 //  . = ALIGN(0x1000);
 753 //  /* The RW PT_LOAD starts here*/
 754 //  rw_sec : { *(rw_sec) }
 755 // would mean that the RW PT_LOAD would become unaligned.
 756 static bool shouldSkip(BaseCommand *Cmd) {
 757   if (isa<OutputSectionCommand>(Cmd))
 758     return false;
 759   if (auto *Assign = dyn_cast<SymbolAssignment>(Cmd))
 760     return Assign->Name != ".";
 761   return true;
 762 }
 763
 764 // Orphan sections are sections present in the input files which are
 765 // not explicitly placed into the output file by the linker script.
 766 //
 767 // When the control reaches this function, Opt.Commands contains
 768 // output section commands for non-orphan sections only. This function
 769 // adds new elements for orphan sections so that all sections are
 770 // explicitly handled by Opt.Commands.
 771 //
 772 // Writer<ELFT>::sortSections has already sorted output sections.
 773 // What we need to do is to scan OutputSections vector and
 774 // Opt.Commands in parallel to find orphan sections. If there is an
 775 // output section that doesn't have a corresponding entry in
 776 // Opt.Commands, we will insert a new entry to Opt.Commands.
 777 //
 778 // There is some ambiguity as to where exactly a new entry should be
 779 // inserted, because Opt.Commands contains not only output section
 780 // commands but also other types of commands such as symbol assignment
 781 // expressions. There's no correct answer here due to the lack of the
 782 // formal specification of the linker script. We use heuristics to
 783 // determine whether a new output command should be added before or
 784 // after another commands. For the details, look at shouldSkip
 785 // function.
 786 void LinkerScript::placeOrphanSections() {
 787   // The OutputSections are already in the correct order.
 788   // This loops creates or moves commands as needed so that they are in the
 789   // correct order.
 790   int CmdIndex = 0;
 791
 792   // As a horrible special case, skip the first . assignment if it is before any
 793   // section. We do this because it is common to set a load address by starting
 794   // the script with ". = 0xabcd" and the expectation is that every section is
 795   // after that.
 796   auto FirstSectionOrDotAssignment =
 797       std::find_if(Opt.Commands.begin(), Opt.Commands.end(),
 798                    [](BaseCommand *Cmd) { return !shouldSkip(Cmd); });
 799   if (FirstSectionOrDotAssignment != Opt.Commands.end()) {
 800     CmdIndex = FirstSectionOrDotAssignment - Opt.Commands.begin();
 801     if (isa<SymbolAssignment>(**FirstSectionOrDotAssignment))
 802       ++CmdIndex;
 803   }
 804
 805   for (OutputSection *Sec : *OutputSections) {
 806     StringRef Name = Sec->Name;
 807
 808     // Find the last spot where we can insert a command and still get the
 809     // correct result.
 810     auto CmdIter = Opt.Commands.begin() + CmdIndex;
 811     auto E = Opt.Commands.end();
 812     while (CmdIter != E && shouldSkip(*CmdIter)) {
 813       ++CmdIter;
 814       ++CmdIndex;
 815     }
 816
 817     // If there is no command corresponding to this output section,
 818     // create one and put a InputSectionDescription in it so that both
 819     // representations agree on which input sections to use.
 820     auto Pos = std::find_if(CmdIter, E, [&](BaseCommand *Base) {
 821       auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
 822       return Cmd && Cmd->Name == Name;
 823     });
 824     if (Pos == E) {
 825       auto *Cmd = make<OutputSectionCommand>(Name);
 826       Opt.Commands.insert(CmdIter, Cmd);
 827       ++CmdIndex;
 828
 829       Cmd->Sec = Sec;
 830       auto *ISD = make<InputSectionDescription>("");
 831       for (InputSection *IS : Sec->Sections)
 832         ISD->Sections.push_back(IS);
 833       Cmd->Commands.push_back(ISD);
 834
 835       continue;
 836     }
 837
 838     // Continue from where we found it.
 839     CmdIndex = (Pos - Opt.Commands.begin()) + 1;
 840   }
 841 }
 842
 843 void LinkerScript::processNonSectionCommands() {
 844   for (BaseCommand *Base : Opt.Commands) {
 845     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base))
 846       assignSymbol(Cmd, false);
 847     else if (auto *Cmd = dyn_cast<AssertCommand>(Base))
 848       Cmd->Expression();
 849   }
 850 }
 851
 852 // Do a last effort at synchronizing the linker script "AST" and the section
 853 // list. This is needed to account for last minute changes, like adding a
 854 // .ARM.exidx terminator and sorting SHF_LINK_ORDER sections.
 855 //
 856 // FIXME: We should instead create the "AST" earlier and the above changes would
 857 // be done directly in the "AST".
 858 //
 859 // This can only handle new sections being added and sections being reordered.
 860 void LinkerScript::synchronize() {
 861   for (BaseCommand *Base : Opt.Commands) {
 862     auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
 863     if (!Cmd)
 864       continue;
 865     ArrayRef<InputSection *> Sections = Cmd->Sec->Sections;
 866     std::vector<InputSectionBase **> ScriptSections;
 867     DenseSet<InputSectionBase *> ScriptSectionsSet;
 868     for (BaseCommand *Base : Cmd->Commands) {
 869       auto *ISD = dyn_cast<InputSectionDescription>(Base);
 870       if (!ISD)
 871         continue;
 872       for (InputSectionBase *&IS : ISD->Sections) {
 873         if (IS->Live) {
 874           ScriptSections.push_back(&IS);
 875           ScriptSectionsSet.insert(IS);
 876         }
 877       }
 878     }
 879     std::vector<InputSectionBase *> Missing;
 880     for (InputSection *IS : Sections)
 881       if (!ScriptSectionsSet.count(IS))
 882         Missing.push_back(IS);
 883     if (!Missing.empty()) {
 884       auto ISD = make<InputSectionDescription>("");
 885       ISD->Sections = Missing;
 886       Cmd->Commands.push_back(ISD);
 887       for (InputSectionBase *&IS : ISD->Sections)
 888         if (IS->Live)
 889           ScriptSections.push_back(&IS);
 890     }
 891     assert(ScriptSections.size() == Sections.size());
 892     for (int I = 0, N = Sections.size(); I < N; ++I)
 893       *ScriptSections[I] = Sections[I];
 894   }
 895 }
 896
 897 void LinkerScript::assignAddresses(std::vector<PhdrEntry> &Phdrs) {
 898   // Assign addresses as instructed by linker script SECTIONS sub-commands.
 899   Dot = 0;
 900   ErrorOnMissingSection = true;
 901   switchTo(Aether);
 902
 903   for (BaseCommand *Base : Opt.Commands) {
 904     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
 905       assignSymbol(Cmd, false);
 906       continue;
 907     }
 908
 909     if (auto *Cmd = dyn_cast<AssertCommand>(Base)) {
 910       Cmd->Expression();
 911       continue;
 912     }
 913
 914     auto *Cmd = cast<OutputSectionCommand>(Base);
 915     assignOffsets(Cmd);
 916   }
 917
 918   uint64_t MinVA = std::numeric_limits<uint64_t>::max();
 919   for (OutputSection *Sec : *OutputSections) {
 920     if (Sec->Flags & SHF_ALLOC)
 921       MinVA = std::min<uint64_t>(MinVA, Sec->Addr);
 922     else
 923       Sec->Addr = 0;
 924   }
 925
 926   allocateHeaders(Phdrs, *OutputSections, MinVA);
 927 }
 928
 929 // Creates program headers as instructed by PHDRS linker script command.
 930 std::vector<PhdrEntry> LinkerScript::createPhdrs() {
 931   std::vector<PhdrEntry> Ret;
 932
 933   // Process PHDRS and FILEHDR keywords because they are not
 934   // real output sections and cannot be added in the following loop.
 935   for (const PhdrsCommand &Cmd : Opt.PhdrsCommands) {
 936     Ret.emplace_back(Cmd.Type, Cmd.Flags == UINT_MAX ? PF_R : Cmd.Flags);
 937     PhdrEntry &Phdr = Ret.back();
 938
 939     if (Cmd.HasFilehdr)
 940       Phdr.add(Out::ElfHeader);
 941     if (Cmd.HasPhdrs)
 942       Phdr.add(Out::ProgramHeaders);
 943
 944     if (Cmd.LMAExpr) {
 945       Phdr.p_paddr = Cmd.LMAExpr().getValue();
 946       Phdr.HasLMA = true;
 947     }
 948   }
 949
 950   // Add output sections to program headers.
 951   for (OutputSection *Sec : *OutputSections) {
 952     if (!(Sec->Flags & SHF_ALLOC))
 953       break;
 954
 955     // Assign headers specified by linker script
 956     for (size_t Id : getPhdrIndices(Sec->Name)) {
 957       Ret[Id].add(Sec);
 958       if (Opt.PhdrsCommands[Id].Flags == UINT_MAX)
 959         Ret[Id].p_flags |= Sec->getPhdrFlags();
 960     }
 961   }
 962   return Ret;
 963 }
 964
 965 bool LinkerScript::ignoreInterpSection() {
 966   // Ignore .interp section in case we have PHDRS specification
 967   // and PT_INTERP isn't listed.
 968   if (Opt.PhdrsCommands.empty())
 969     return false;
 970   for (PhdrsCommand &Cmd : Opt.PhdrsCommands)
 971     if (Cmd.Type == PT_INTERP)
 972       return false;
 973   return true;
 974 }
 975
 976 Optional<uint32_t> LinkerScript::getFiller(StringRef Name) {
 977   for (BaseCommand *Base : Opt.Commands)
 978     if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
 979       if (Cmd->Name == Name)
 980         return Cmd->Filler;
 981   return None;
 982 }
 983
 984 static void writeInt(uint8_t *Buf, uint64_t Data, uint64_t Size) {
 985   if (Size == 1)
 986     *Buf = Data;
 987   else if (Size == 2)
 988     write16(Buf, Data, Config->Endianness);
 989   else if (Size == 4)
 990     write32(Buf, Data, Config->Endianness);
 991   else if (Size == 8)
 992     write64(Buf, Data, Config->Endianness);
 993   else
 994     llvm_unreachable("unsupported Size argument");
 995 }
 996
 997 void LinkerScript::writeDataBytes(StringRef Name, uint8_t *Buf) {
 998   int I = getSectionIndex(Name);
 999   if (I == INT_MAX)
1000     return;
1001
1002   auto *Cmd = dyn_cast<OutputSectionCommand>(Opt.Commands[I]);
1003   for (BaseCommand *Base : Cmd->Commands)
1004     if (auto *Data = dyn_cast<BytesDataCommand>(Base))
1005       writeInt(Buf + Data->Offset, Data->Expression().getValue(), Data->Size);
1006 }
1007
1008 bool LinkerScript::hasLMA(StringRef Name) {
1009   for (BaseCommand *Base : Opt.Commands)
1010     if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
1011       if (Cmd->LMAExpr && Cmd->Name == Name)
1012         return true;
1013   return false;
1014 }
1015
1016 // Returns the index of the given section name in linker script
1017 // SECTIONS commands. Sections are laid out as the same order as they
1018 // were in the script. If a given name did not appear in the script,
1019 // it returns INT_MAX, so that it will be laid out at end of file.
1020 int LinkerScript::getSectionIndex(StringRef Name) {
1021   for (int I = 0, E = Opt.Commands.size(); I != E; ++I)
1022     if (auto *Cmd = dyn_cast<OutputSectionCommand>(Opt.Commands[I]))
1023       if (Cmd->Name == Name)
1024         return I;
1025   return INT_MAX;
1026 }
1027
1028 ExprValue LinkerScript::getSymbolValue(const Twine &Loc, StringRef S) {
1029   if (S == ".")
1030     return {CurOutSec, Dot - CurOutSec->Addr};
1031   if (SymbolBody *B = findSymbol(S)) {
1032     if (auto *D = dyn_cast<DefinedRegular>(B))
1033       return {D->Section, D->Value};
1034     if (auto *C = dyn_cast<DefinedCommon>(B))
1035       return {InX::Common, C->Offset};
1036   }
1037   error(Loc + ": symbol not found: " + S);
1038   return 0;
1039 }
1040
1041 bool LinkerScript::isDefined(StringRef S) { return findSymbol(S) != nullptr; }
1042
1043 // Returns indices of ELF headers containing specific section, identified
1044 // by Name. Each index is a zero based number of ELF header listed within
1045 // PHDRS {} script block.
1046 std::vector<size_t> LinkerScript::getPhdrIndices(StringRef SectionName) {
1047   for (BaseCommand *Base : Opt.Commands) {
1048     auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
1049     if (!Cmd || Cmd->Name != SectionName)
1050       continue;
1051
1052     std::vector<size_t> Ret;
1053     for (StringRef PhdrName : Cmd->Phdrs)
1054       Ret.push_back(getPhdrIndex(Cmd->Location, PhdrName));
1055     return Ret;
1056   }
1057   return {};
1058 }
1059
1060 size_t LinkerScript::getPhdrIndex(const Twine &Loc, StringRef PhdrName) {
1061   size_t I = 0;
1062   for (PhdrsCommand &Cmd : Opt.PhdrsCommands) {
1063     if (Cmd.Name == PhdrName)
1064       return I;
1065     ++I;
1066   }
1067   error(Loc + ": section header '" + PhdrName + "' is not listed in PHDRS");
1068   return 0;
1069 }