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