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