1 //===- LinkerScript.cpp ---------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file contains the parser/evaluator of the linker script. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "LinkerScript.h" 14 #include "Config.h" 15 #include "InputSection.h" 16 #include "OutputSections.h" 17 #include "SymbolTable.h" 18 #include "Symbols.h" 19 #include "SyntheticSections.h" 20 #include "Target.h" 21 #include "Writer.h" 22 #include "lld/Common/Memory.h" 23 #include "lld/Common/Strings.h" 24 #include "lld/Common/Threads.h" 25 #include "llvm/ADT/STLExtras.h" 26 #include "llvm/ADT/StringRef.h" 27 #include "llvm/BinaryFormat/ELF.h" 28 #include "llvm/Support/Casting.h" 29 #include "llvm/Support/Endian.h" 30 #include "llvm/Support/ErrorHandling.h" 31 #include "llvm/Support/FileSystem.h" 32 #include "llvm/Support/Path.h" 33 #include <algorithm> 34 #include <cassert> 35 #include <cstddef> 36 #include <cstdint> 37 #include <iterator> 38 #include <limits> 39 #include <string> 40 #include <vector> 41 42 using namespace llvm; 43 using namespace llvm::ELF; 44 using namespace llvm::object; 45 using namespace llvm::support::endian; 46 47 namespace lld { 48 namespace elf { 49 LinkerScript *script; 50 51 static uint64_t getOutputSectionVA(SectionBase *sec) { 52 OutputSection *os = sec->getOutputSection(); 53 assert(os && "input section has no output section assigned"); 54 return os ? os->addr : 0; 55 } 56 57 uint64_t ExprValue::getValue() const { 58 if (sec) 59 return alignTo(sec->getOffset(val) + getOutputSectionVA(sec), 60 alignment); 61 return alignTo(val, alignment); 62 } 63 64 uint64_t ExprValue::getSecAddr() const { 65 if (sec) 66 return sec->getOffset(0) + getOutputSectionVA(sec); 67 return 0; 68 } 69 70 uint64_t ExprValue::getSectionOffset() const { 71 // If the alignment is trivial, we don't have to compute the full 72 // value to know the offset. This allows this function to succeed in 73 // cases where the output section is not yet known. 74 if (alignment == 1 && !sec) 75 return val; 76 return getValue() - getSecAddr(); 77 } 78 79 OutputSection *LinkerScript::createOutputSection(StringRef name, 80 StringRef location) { 81 OutputSection *&secRef = nameToOutputSection[name]; 82 OutputSection *sec; 83 if (secRef && secRef->location.empty()) { 84 // There was a forward reference. 85 sec = secRef; 86 } else { 87 sec = make<OutputSection>(name, SHT_PROGBITS, 0); 88 if (!secRef) 89 secRef = sec; 90 } 91 sec->location = location; 92 return sec; 93 } 94 95 OutputSection *LinkerScript::getOrCreateOutputSection(StringRef name) { 96 OutputSection *&cmdRef = nameToOutputSection[name]; 97 if (!cmdRef) 98 cmdRef = make<OutputSection>(name, SHT_PROGBITS, 0); 99 return cmdRef; 100 } 101 102 // Expands the memory region by the specified size. 103 static void expandMemoryRegion(MemoryRegion *memRegion, uint64_t size, 104 StringRef regionName, StringRef secName) { 105 memRegion->curPos += size; 106 uint64_t newSize = memRegion->curPos - memRegion->origin; 107 if (newSize > memRegion->length) 108 error("section '" + secName + "' will not fit in region '" + regionName + 109 "': overflowed by " + Twine(newSize - memRegion->length) + " bytes"); 110 } 111 112 void LinkerScript::expandMemoryRegions(uint64_t size) { 113 if (ctx->memRegion) 114 expandMemoryRegion(ctx->memRegion, size, ctx->memRegion->name, 115 ctx->outSec->name); 116 // Only expand the LMARegion if it is different from memRegion. 117 if (ctx->lmaRegion && ctx->memRegion != ctx->lmaRegion) 118 expandMemoryRegion(ctx->lmaRegion, size, ctx->lmaRegion->name, 119 ctx->outSec->name); 120 } 121 122 void LinkerScript::expandOutputSection(uint64_t size) { 123 ctx->outSec->size += size; 124 expandMemoryRegions(size); 125 } 126 127 void LinkerScript::setDot(Expr e, const Twine &loc, bool inSec) { 128 uint64_t val = e().getValue(); 129 if (val < dot && inSec) 130 error(loc + ": unable to move location counter backward for: " + 131 ctx->outSec->name); 132 133 // Update to location counter means update to section size. 134 if (inSec) 135 expandOutputSection(val - dot); 136 137 dot = val; 138 } 139 140 // Used for handling linker symbol assignments, for both finalizing 141 // their values and doing early declarations. Returns true if symbol 142 // should be defined from linker script. 143 static bool shouldDefineSym(SymbolAssignment *cmd) { 144 if (cmd->name == ".") 145 return false; 146 147 if (!cmd->provide) 148 return true; 149 150 // If a symbol was in PROVIDE(), we need to define it only 151 // when it is a referenced undefined symbol. 152 Symbol *b = symtab->find(cmd->name); 153 if (b && !b->isDefined()) 154 return true; 155 return false; 156 } 157 158 // Called by processSymbolAssignments() to assign definitions to 159 // linker-script-defined symbols. 160 void LinkerScript::addSymbol(SymbolAssignment *cmd) { 161 if (!shouldDefineSym(cmd)) 162 return; 163 164 // Define a symbol. 165 ExprValue value = cmd->expression(); 166 SectionBase *sec = value.isAbsolute() ? nullptr : value.sec; 167 uint8_t visibility = cmd->hidden ? STV_HIDDEN : STV_DEFAULT; 168 169 // When this function is called, section addresses have not been 170 // fixed yet. So, we may or may not know the value of the RHS 171 // expression. 172 // 173 // For example, if an expression is `x = 42`, we know x is always 42. 174 // However, if an expression is `x = .`, there's no way to know its 175 // value at the moment. 176 // 177 // We want to set symbol values early if we can. This allows us to 178 // use symbols as variables in linker scripts. Doing so allows us to 179 // write expressions like this: `alignment = 16; . = ALIGN(., alignment)`. 180 uint64_t symValue = value.sec ? 0 : value.getValue(); 181 182 Defined newSym(nullptr, cmd->name, STB_GLOBAL, visibility, STT_NOTYPE, 183 symValue, 0, sec); 184 185 Symbol *sym = symtab->insert(cmd->name); 186 sym->mergeProperties(newSym); 187 sym->replace(newSym); 188 cmd->sym = cast<Defined>(sym); 189 } 190 191 // This function is called from LinkerScript::declareSymbols. 192 // It creates a placeholder symbol if needed. 193 static void declareSymbol(SymbolAssignment *cmd) { 194 if (!shouldDefineSym(cmd)) 195 return; 196 197 uint8_t visibility = cmd->hidden ? STV_HIDDEN : STV_DEFAULT; 198 Defined newSym(nullptr, cmd->name, STB_GLOBAL, visibility, STT_NOTYPE, 0, 0, 199 nullptr); 200 201 // We can't calculate final value right now. 202 Symbol *sym = symtab->insert(cmd->name); 203 sym->mergeProperties(newSym); 204 sym->replace(newSym); 205 206 cmd->sym = cast<Defined>(sym); 207 cmd->provide = false; 208 sym->scriptDefined = true; 209 } 210 211 using SymbolAssignmentMap = 212 DenseMap<const Defined *, std::pair<SectionBase *, uint64_t>>; 213 214 // Collect section/value pairs of linker-script-defined symbols. This is used to 215 // check whether symbol values converge. 216 static SymbolAssignmentMap 217 getSymbolAssignmentValues(const std::vector<BaseCommand *> §ionCommands) { 218 SymbolAssignmentMap ret; 219 for (BaseCommand *base : sectionCommands) { 220 if (auto *cmd = dyn_cast<SymbolAssignment>(base)) { 221 if (cmd->sym) // sym is nullptr for dot. 222 ret.try_emplace(cmd->sym, 223 std::make_pair(cmd->sym->section, cmd->sym->value)); 224 continue; 225 } 226 for (BaseCommand *sub_base : cast<OutputSection>(base)->sectionCommands) 227 if (auto *cmd = dyn_cast<SymbolAssignment>(sub_base)) 228 if (cmd->sym) 229 ret.try_emplace(cmd->sym, 230 std::make_pair(cmd->sym->section, cmd->sym->value)); 231 } 232 return ret; 233 } 234 235 // Returns the lexicographical smallest (for determinism) Defined whose 236 // section/value has changed. 237 static const Defined * 238 getChangedSymbolAssignment(const SymbolAssignmentMap &oldValues) { 239 const Defined *changed = nullptr; 240 for (auto &it : oldValues) { 241 const Defined *sym = it.first; 242 if (std::make_pair(sym->section, sym->value) != it.second && 243 (!changed || sym->getName() < changed->getName())) 244 changed = sym; 245 } 246 return changed; 247 } 248 249 // This method is used to handle INSERT AFTER statement. Here we rebuild 250 // the list of script commands to mix sections inserted into. 251 void LinkerScript::processInsertCommands() { 252 std::vector<BaseCommand *> v; 253 auto insert = [&](std::vector<BaseCommand *> &from) { 254 v.insert(v.end(), from.begin(), from.end()); 255 from.clear(); 256 }; 257 258 for (BaseCommand *base : sectionCommands) { 259 if (auto *os = dyn_cast<OutputSection>(base)) { 260 insert(insertBeforeCommands[os->name]); 261 v.push_back(base); 262 insert(insertAfterCommands[os->name]); 263 continue; 264 } 265 v.push_back(base); 266 } 267 268 for (auto &cmds : {insertBeforeCommands, insertAfterCommands}) 269 for (const std::pair<StringRef, std::vector<BaseCommand *>> &p : cmds) 270 if (!p.second.empty()) 271 error("unable to INSERT AFTER/BEFORE " + p.first + 272 ": section not defined"); 273 274 sectionCommands = std::move(v); 275 } 276 277 // Symbols defined in script should not be inlined by LTO. At the same time 278 // we don't know their final values until late stages of link. Here we scan 279 // over symbol assignment commands and create placeholder symbols if needed. 280 void LinkerScript::declareSymbols() { 281 assert(!ctx); 282 for (BaseCommand *base : sectionCommands) { 283 if (auto *cmd = dyn_cast<SymbolAssignment>(base)) { 284 declareSymbol(cmd); 285 continue; 286 } 287 288 // If the output section directive has constraints, 289 // we can't say for sure if it is going to be included or not. 290 // Skip such sections for now. Improve the checks if we ever 291 // need symbols from that sections to be declared early. 292 auto *sec = cast<OutputSection>(base); 293 if (sec->constraint != ConstraintKind::NoConstraint) 294 continue; 295 for (BaseCommand *base2 : sec->sectionCommands) 296 if (auto *cmd = dyn_cast<SymbolAssignment>(base2)) 297 declareSymbol(cmd); 298 } 299 } 300 301 // This function is called from assignAddresses, while we are 302 // fixing the output section addresses. This function is supposed 303 // to set the final value for a given symbol assignment. 304 void LinkerScript::assignSymbol(SymbolAssignment *cmd, bool inSec) { 305 if (cmd->name == ".") { 306 setDot(cmd->expression, cmd->location, inSec); 307 return; 308 } 309 310 if (!cmd->sym) 311 return; 312 313 ExprValue v = cmd->expression(); 314 if (v.isAbsolute()) { 315 cmd->sym->section = nullptr; 316 cmd->sym->value = v.getValue(); 317 } else { 318 cmd->sym->section = v.sec; 319 cmd->sym->value = v.getSectionOffset(); 320 } 321 } 322 323 static std::string getFilename(InputFile *file) { 324 if (!file) 325 return ""; 326 if (file->archiveName.empty()) 327 return file->getName(); 328 return (file->archiveName + "(" + file->getName() + ")").str(); 329 } 330 331 bool LinkerScript::shouldKeep(InputSectionBase *s) { 332 if (keptSections.empty()) 333 return false; 334 std::string filename = getFilename(s->file); 335 for (InputSectionDescription *id : keptSections) 336 if (id->filePat.match(filename)) 337 for (SectionPattern &p : id->sectionPatterns) 338 if (p.sectionPat.match(s->name)) 339 return true; 340 return false; 341 } 342 343 // A helper function for the SORT() command. 344 static bool matchConstraints(ArrayRef<InputSectionBase *> sections, 345 ConstraintKind kind) { 346 if (kind == ConstraintKind::NoConstraint) 347 return true; 348 349 bool isRW = llvm::any_of( 350 sections, [](InputSectionBase *sec) { return sec->flags & SHF_WRITE; }); 351 352 return (isRW && kind == ConstraintKind::ReadWrite) || 353 (!isRW && kind == ConstraintKind::ReadOnly); 354 } 355 356 static void sortSections(MutableArrayRef<InputSectionBase *> vec, 357 SortSectionPolicy k) { 358 auto alignmentComparator = [](InputSectionBase *a, InputSectionBase *b) { 359 // ">" is not a mistake. Sections with larger alignments are placed 360 // before sections with smaller alignments in order to reduce the 361 // amount of padding necessary. This is compatible with GNU. 362 return a->alignment > b->alignment; 363 }; 364 auto nameComparator = [](InputSectionBase *a, InputSectionBase *b) { 365 return a->name < b->name; 366 }; 367 auto priorityComparator = [](InputSectionBase *a, InputSectionBase *b) { 368 return getPriority(a->name) < getPriority(b->name); 369 }; 370 371 switch (k) { 372 case SortSectionPolicy::Default: 373 case SortSectionPolicy::None: 374 return; 375 case SortSectionPolicy::Alignment: 376 return llvm::stable_sort(vec, alignmentComparator); 377 case SortSectionPolicy::Name: 378 return llvm::stable_sort(vec, nameComparator); 379 case SortSectionPolicy::Priority: 380 return llvm::stable_sort(vec, priorityComparator); 381 } 382 } 383 384 // Sort sections as instructed by SORT-family commands and --sort-section 385 // option. Because SORT-family commands can be nested at most two depth 386 // (e.g. SORT_BY_NAME(SORT_BY_ALIGNMENT(.text.*))) and because the command 387 // line option is respected even if a SORT command is given, the exact 388 // behavior we have here is a bit complicated. Here are the rules. 389 // 390 // 1. If two SORT commands are given, --sort-section is ignored. 391 // 2. If one SORT command is given, and if it is not SORT_NONE, 392 // --sort-section is handled as an inner SORT command. 393 // 3. If one SORT command is given, and if it is SORT_NONE, don't sort. 394 // 4. If no SORT command is given, sort according to --sort-section. 395 static void sortInputSections(MutableArrayRef<InputSectionBase *> vec, 396 const SectionPattern &pat) { 397 if (pat.sortOuter == SortSectionPolicy::None) 398 return; 399 400 if (pat.sortInner == SortSectionPolicy::Default) 401 sortSections(vec, config->sortSection); 402 else 403 sortSections(vec, pat.sortInner); 404 sortSections(vec, pat.sortOuter); 405 } 406 407 // Compute and remember which sections the InputSectionDescription matches. 408 std::vector<InputSectionBase *> 409 LinkerScript::computeInputSections(const InputSectionDescription *cmd) { 410 std::vector<InputSectionBase *> ret; 411 412 // Collects all sections that satisfy constraints of Cmd. 413 for (const SectionPattern &pat : cmd->sectionPatterns) { 414 size_t sizeBefore = ret.size(); 415 416 for (InputSectionBase *sec : inputSections) { 417 if (!sec->isLive() || sec->parent) 418 continue; 419 420 // For -emit-relocs we have to ignore entries like 421 // .rela.dyn : { *(.rela.data) } 422 // which are common because they are in the default bfd script. 423 // We do not ignore SHT_REL[A] linker-synthesized sections here because 424 // want to support scripts that do custom layout for them. 425 if (isa<InputSection>(sec) && 426 cast<InputSection>(sec)->getRelocatedSection()) 427 continue; 428 429 std::string filename = getFilename(sec->file); 430 if (!cmd->filePat.match(filename) || 431 pat.excludedFilePat.match(filename) || 432 !pat.sectionPat.match(sec->name)) 433 continue; 434 435 ret.push_back(sec); 436 } 437 438 sortInputSections( 439 MutableArrayRef<InputSectionBase *>(ret).slice(sizeBefore), pat); 440 } 441 return ret; 442 } 443 444 void LinkerScript::discard(InputSectionBase *s) { 445 if (s == in.shStrTab || s == mainPart->relaDyn || s == mainPart->relrDyn) 446 error("discarding " + s->name + " section is not allowed"); 447 448 // You can discard .hash and .gnu.hash sections by linker scripts. Since 449 // they are synthesized sections, we need to handle them differently than 450 // other regular sections. 451 if (s == mainPart->gnuHashTab) 452 mainPart->gnuHashTab = nullptr; 453 if (s == mainPart->hashTab) 454 mainPart->hashTab = nullptr; 455 456 s->markDead(); 457 s->parent = nullptr; 458 for (InputSection *ds : s->dependentSections) 459 discard(ds); 460 } 461 462 std::vector<InputSectionBase *> 463 LinkerScript::createInputSectionList(OutputSection &outCmd) { 464 std::vector<InputSectionBase *> ret; 465 466 for (BaseCommand *base : outCmd.sectionCommands) { 467 if (auto *cmd = dyn_cast<InputSectionDescription>(base)) { 468 cmd->sectionBases = computeInputSections(cmd); 469 for (InputSectionBase *s : cmd->sectionBases) 470 s->parent = &outCmd; 471 ret.insert(ret.end(), cmd->sectionBases.begin(), cmd->sectionBases.end()); 472 } 473 } 474 return ret; 475 } 476 477 // Create output sections described by SECTIONS commands. 478 void LinkerScript::processSectionCommands() { 479 size_t i = 0; 480 for (BaseCommand *base : sectionCommands) { 481 if (auto *sec = dyn_cast<OutputSection>(base)) { 482 std::vector<InputSectionBase *> v = createInputSectionList(*sec); 483 484 // The output section name `/DISCARD/' is special. 485 // Any input section assigned to it is discarded. 486 if (sec->name == "/DISCARD/") { 487 for (InputSectionBase *s : v) 488 discard(s); 489 sec->sectionCommands.clear(); 490 continue; 491 } 492 493 // This is for ONLY_IF_RO and ONLY_IF_RW. An output section directive 494 // ".foo : ONLY_IF_R[OW] { ... }" is handled only if all member input 495 // sections satisfy a given constraint. If not, a directive is handled 496 // as if it wasn't present from the beginning. 497 // 498 // Because we'll iterate over SectionCommands many more times, the easy 499 // way to "make it as if it wasn't present" is to make it empty. 500 if (!matchConstraints(v, sec->constraint)) { 501 for (InputSectionBase *s : v) 502 s->parent = nullptr; 503 sec->sectionCommands.clear(); 504 continue; 505 } 506 507 // Handle subalign (e.g. ".foo : SUBALIGN(32) { ... }"). If subalign 508 // is given, input sections are aligned to that value, whether the 509 // given value is larger or smaller than the original section alignment. 510 if (sec->subalignExpr) { 511 uint32_t subalign = sec->subalignExpr().getValue(); 512 for (InputSectionBase *s : v) 513 s->alignment = subalign; 514 } 515 516 // Set the partition field the same way OutputSection::recordSection() 517 // does. Partitions cannot be used with the SECTIONS command, so this is 518 // always 1. 519 sec->partition = 1; 520 521 sec->sectionIndex = i++; 522 } 523 } 524 } 525 526 void LinkerScript::processSymbolAssignments() { 527 // Dot outside an output section still represents a relative address, whose 528 // sh_shndx should not be SHN_UNDEF or SHN_ABS. Create a dummy aether section 529 // that fills the void outside a section. It has an index of one, which is 530 // indistinguishable from any other regular section index. 531 aether = make<OutputSection>("", 0, SHF_ALLOC); 532 aether->sectionIndex = 1; 533 534 // ctx captures the local AddressState and makes it accessible deliberately. 535 // This is needed as there are some cases where we cannot just thread the 536 // current state through to a lambda function created by the script parser. 537 AddressState state; 538 ctx = &state; 539 ctx->outSec = aether; 540 541 for (BaseCommand *base : sectionCommands) { 542 if (auto *cmd = dyn_cast<SymbolAssignment>(base)) 543 addSymbol(cmd); 544 else 545 for (BaseCommand *sub_base : cast<OutputSection>(base)->sectionCommands) 546 if (auto *cmd = dyn_cast<SymbolAssignment>(sub_base)) 547 addSymbol(cmd); 548 } 549 550 ctx = nullptr; 551 } 552 553 static OutputSection *findByName(ArrayRef<BaseCommand *> vec, 554 StringRef name) { 555 for (BaseCommand *base : vec) 556 if (auto *sec = dyn_cast<OutputSection>(base)) 557 if (sec->name == name) 558 return sec; 559 return nullptr; 560 } 561 562 static OutputSection *createSection(InputSectionBase *isec, 563 StringRef outsecName) { 564 OutputSection *sec = script->createOutputSection(outsecName, "<internal>"); 565 sec->recordSection(isec); 566 return sec; 567 } 568 569 static OutputSection * 570 addInputSec(StringMap<TinyPtrVector<OutputSection *>> &map, 571 InputSectionBase *isec, StringRef outsecName) { 572 // Sections with SHT_GROUP or SHF_GROUP attributes reach here only when the -r 573 // option is given. A section with SHT_GROUP defines a "section group", and 574 // its members have SHF_GROUP attribute. Usually these flags have already been 575 // stripped by InputFiles.cpp as section groups are processed and uniquified. 576 // However, for the -r option, we want to pass through all section groups 577 // as-is because adding/removing members or merging them with other groups 578 // change their semantics. 579 if (isec->type == SHT_GROUP || (isec->flags & SHF_GROUP)) 580 return createSection(isec, outsecName); 581 582 // Imagine .zed : { *(.foo) *(.bar) } script. Both foo and bar may have 583 // relocation sections .rela.foo and .rela.bar for example. Most tools do 584 // not allow multiple REL[A] sections for output section. Hence we 585 // should combine these relocation sections into single output. 586 // We skip synthetic sections because it can be .rela.dyn/.rela.plt or any 587 // other REL[A] sections created by linker itself. 588 if (!isa<SyntheticSection>(isec) && 589 (isec->type == SHT_REL || isec->type == SHT_RELA)) { 590 auto *sec = cast<InputSection>(isec); 591 OutputSection *out = sec->getRelocatedSection()->getOutputSection(); 592 593 if (out->relocationSection) { 594 out->relocationSection->recordSection(sec); 595 return nullptr; 596 } 597 598 out->relocationSection = createSection(isec, outsecName); 599 return out->relocationSection; 600 } 601 602 // The ELF spec just says 603 // ---------------------------------------------------------------- 604 // In the first phase, input sections that match in name, type and 605 // attribute flags should be concatenated into single sections. 606 // ---------------------------------------------------------------- 607 // 608 // However, it is clear that at least some flags have to be ignored for 609 // section merging. At the very least SHF_GROUP and SHF_COMPRESSED have to be 610 // ignored. We should not have two output .text sections just because one was 611 // in a group and another was not for example. 612 // 613 // It also seems that wording was a late addition and didn't get the 614 // necessary scrutiny. 615 // 616 // Merging sections with different flags is expected by some users. One 617 // reason is that if one file has 618 // 619 // int *const bar __attribute__((section(".foo"))) = (int *)0; 620 // 621 // gcc with -fPIC will produce a read only .foo section. But if another 622 // file has 623 // 624 // int zed; 625 // int *const bar __attribute__((section(".foo"))) = (int *)&zed; 626 // 627 // gcc with -fPIC will produce a read write section. 628 // 629 // Last but not least, when using linker script the merge rules are forced by 630 // the script. Unfortunately, linker scripts are name based. This means that 631 // expressions like *(.foo*) can refer to multiple input sections with 632 // different flags. We cannot put them in different output sections or we 633 // would produce wrong results for 634 // 635 // start = .; *(.foo.*) end = .; *(.bar) 636 // 637 // and a mapping of .foo1 and .bar1 to one section and .foo2 and .bar2 to 638 // another. The problem is that there is no way to layout those output 639 // sections such that the .foo sections are the only thing between the start 640 // and end symbols. 641 // 642 // Given the above issues, we instead merge sections by name and error on 643 // incompatible types and flags. 644 TinyPtrVector<OutputSection *> &v = map[outsecName]; 645 for (OutputSection *sec : v) { 646 if (sec->partition != isec->partition) 647 continue; 648 649 if (config->relocatable && (isec->flags & SHF_LINK_ORDER)) { 650 // Merging two SHF_LINK_ORDER sections with different sh_link fields will 651 // change their semantics, so we only merge them in -r links if they will 652 // end up being linked to the same output section. The casts are fine 653 // because everything in the map was created by the orphan placement code. 654 auto *firstIsec = cast<InputSectionBase>( 655 cast<InputSectionDescription>(sec->sectionCommands[0]) 656 ->sectionBases[0]); 657 if (firstIsec->getLinkOrderDep()->getOutputSection() != 658 isec->getLinkOrderDep()->getOutputSection()) 659 continue; 660 } 661 662 sec->recordSection(isec); 663 return nullptr; 664 } 665 666 OutputSection *sec = createSection(isec, outsecName); 667 v.push_back(sec); 668 return sec; 669 } 670 671 // Add sections that didn't match any sections command. 672 void LinkerScript::addOrphanSections() { 673 StringMap<TinyPtrVector<OutputSection *>> map; 674 std::vector<OutputSection *> v; 675 676 std::function<void(InputSectionBase *)> add; 677 add = [&](InputSectionBase *s) { 678 if (s->isLive() && !s->parent) { 679 StringRef name = getOutputSectionName(s); 680 681 if (config->orphanHandling == OrphanHandlingPolicy::Error) 682 error(toString(s) + " is being placed in '" + name + "'"); 683 else if (config->orphanHandling == OrphanHandlingPolicy::Warn) 684 warn(toString(s) + " is being placed in '" + name + "'"); 685 686 if (OutputSection *sec = findByName(sectionCommands, name)) { 687 sec->recordSection(s); 688 } else { 689 if (OutputSection *os = addInputSec(map, s, name)) 690 v.push_back(os); 691 assert(isa<MergeInputSection>(s) || 692 s->getOutputSection()->sectionIndex == UINT32_MAX); 693 } 694 } 695 696 if (config->relocatable) 697 for (InputSectionBase *depSec : s->dependentSections) 698 if (depSec->flags & SHF_LINK_ORDER) 699 add(depSec); 700 }; 701 702 // For futher --emit-reloc handling code we need target output section 703 // to be created before we create relocation output section, so we want 704 // to create target sections first. We do not want priority handling 705 // for synthetic sections because them are special. 706 for (InputSectionBase *isec : inputSections) { 707 // In -r links, SHF_LINK_ORDER sections are added while adding their parent 708 // sections because we need to know the parent's output section before we 709 // can select an output section for the SHF_LINK_ORDER section. 710 if (config->relocatable && (isec->flags & SHF_LINK_ORDER)) 711 continue; 712 713 if (auto *sec = dyn_cast<InputSection>(isec)) 714 if (InputSectionBase *rel = sec->getRelocatedSection()) 715 if (auto *relIS = dyn_cast_or_null<InputSectionBase>(rel->parent)) 716 add(relIS); 717 add(isec); 718 } 719 720 // If no SECTIONS command was given, we should insert sections commands 721 // before others, so that we can handle scripts which refers them, 722 // for example: "foo = ABSOLUTE(ADDR(.text)));". 723 // When SECTIONS command is present we just add all orphans to the end. 724 if (hasSectionsCommand) 725 sectionCommands.insert(sectionCommands.end(), v.begin(), v.end()); 726 else 727 sectionCommands.insert(sectionCommands.begin(), v.begin(), v.end()); 728 } 729 730 uint64_t LinkerScript::advance(uint64_t size, unsigned alignment) { 731 bool isTbss = 732 (ctx->outSec->flags & SHF_TLS) && ctx->outSec->type == SHT_NOBITS; 733 uint64_t start = isTbss ? dot + ctx->threadBssOffset : dot; 734 start = alignTo(start, alignment); 735 uint64_t end = start + size; 736 737 if (isTbss) 738 ctx->threadBssOffset = end - dot; 739 else 740 dot = end; 741 return end; 742 } 743 744 void LinkerScript::output(InputSection *s) { 745 assert(ctx->outSec == s->getParent()); 746 uint64_t before = advance(0, 1); 747 uint64_t pos = advance(s->getSize(), s->alignment); 748 s->outSecOff = pos - s->getSize() - ctx->outSec->addr; 749 750 // Update output section size after adding each section. This is so that 751 // SIZEOF works correctly in the case below: 752 // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) } 753 expandOutputSection(pos - before); 754 } 755 756 void LinkerScript::switchTo(OutputSection *sec) { 757 ctx->outSec = sec; 758 759 uint64_t before = advance(0, 1); 760 ctx->outSec->addr = advance(0, ctx->outSec->alignment); 761 expandMemoryRegions(ctx->outSec->addr - before); 762 } 763 764 // This function searches for a memory region to place the given output 765 // section in. If found, a pointer to the appropriate memory region is 766 // returned. Otherwise, a nullptr is returned. 767 MemoryRegion *LinkerScript::findMemoryRegion(OutputSection *sec) { 768 // If a memory region name was specified in the output section command, 769 // then try to find that region first. 770 if (!sec->memoryRegionName.empty()) { 771 if (MemoryRegion *m = memoryRegions.lookup(sec->memoryRegionName)) 772 return m; 773 error("memory region '" + sec->memoryRegionName + "' not declared"); 774 return nullptr; 775 } 776 777 // If at least one memory region is defined, all sections must 778 // belong to some memory region. Otherwise, we don't need to do 779 // anything for memory regions. 780 if (memoryRegions.empty()) 781 return nullptr; 782 783 // See if a region can be found by matching section flags. 784 for (auto &pair : memoryRegions) { 785 MemoryRegion *m = pair.second; 786 if ((m->flags & sec->flags) && (m->negFlags & sec->flags) == 0) 787 return m; 788 } 789 790 // Otherwise, no suitable region was found. 791 if (sec->flags & SHF_ALLOC) 792 error("no memory region specified for section '" + sec->name + "'"); 793 return nullptr; 794 } 795 796 static OutputSection *findFirstSection(PhdrEntry *load) { 797 for (OutputSection *sec : outputSections) 798 if (sec->ptLoad == load) 799 return sec; 800 return nullptr; 801 } 802 803 // This function assigns offsets to input sections and an output section 804 // for a single sections command (e.g. ".text { *(.text); }"). 805 void LinkerScript::assignOffsets(OutputSection *sec) { 806 if (!(sec->flags & SHF_ALLOC)) 807 dot = 0; 808 809 ctx->memRegion = sec->memRegion; 810 ctx->lmaRegion = sec->lmaRegion; 811 if (ctx->memRegion) 812 dot = ctx->memRegion->curPos; 813 814 if ((sec->flags & SHF_ALLOC) && sec->addrExpr) 815 setDot(sec->addrExpr, sec->location, false); 816 817 // If the address of the section has been moved forward by an explicit 818 // expression so that it now starts past the current curPos of the enclosing 819 // region, we need to expand the current region to account for the space 820 // between the previous section, if any, and the start of this section. 821 if (ctx->memRegion && ctx->memRegion->curPos < dot) 822 expandMemoryRegion(ctx->memRegion, dot - ctx->memRegion->curPos, 823 ctx->memRegion->name, sec->name); 824 825 switchTo(sec); 826 827 if (sec->lmaExpr) 828 ctx->lmaOffset = sec->lmaExpr().getValue() - dot; 829 830 if (MemoryRegion *mr = sec->lmaRegion) 831 ctx->lmaOffset = mr->curPos - dot; 832 833 // If neither AT nor AT> is specified for an allocatable section, the linker 834 // will set the LMA such that the difference between VMA and LMA for the 835 // section is the same as the preceding output section in the same region 836 // https://sourceware.org/binutils/docs-2.20/ld/Output-Section-LMA.html 837 // This, however, should only be done by the first "non-header" section 838 // in the segment. 839 if (PhdrEntry *l = ctx->outSec->ptLoad) 840 if (sec == findFirstSection(l)) 841 l->lmaOffset = ctx->lmaOffset; 842 843 // We can call this method multiple times during the creation of 844 // thunks and want to start over calculation each time. 845 sec->size = 0; 846 847 // We visited SectionsCommands from processSectionCommands to 848 // layout sections. Now, we visit SectionsCommands again to fix 849 // section offsets. 850 for (BaseCommand *base : sec->sectionCommands) { 851 // This handles the assignments to symbol or to the dot. 852 if (auto *cmd = dyn_cast<SymbolAssignment>(base)) { 853 cmd->addr = dot; 854 assignSymbol(cmd, true); 855 cmd->size = dot - cmd->addr; 856 continue; 857 } 858 859 // Handle BYTE(), SHORT(), LONG(), or QUAD(). 860 if (auto *cmd = dyn_cast<ByteCommand>(base)) { 861 cmd->offset = dot - ctx->outSec->addr; 862 dot += cmd->size; 863 expandOutputSection(cmd->size); 864 continue; 865 } 866 867 // Handle a single input section description command. 868 // It calculates and assigns the offsets for each section and also 869 // updates the output section size. 870 for (InputSection *sec : cast<InputSectionDescription>(base)->sections) 871 output(sec); 872 } 873 } 874 875 static bool isDiscardable(OutputSection &sec) { 876 if (sec.name == "/DISCARD/") 877 return true; 878 879 // We do not remove empty sections that are explicitly 880 // assigned to any segment. 881 if (!sec.phdrs.empty()) 882 return false; 883 884 // We do not want to remove OutputSections with expressions that reference 885 // symbols even if the OutputSection is empty. We want to ensure that the 886 // expressions can be evaluated and report an error if they cannot. 887 if (sec.expressionsUseSymbols) 888 return false; 889 890 // OutputSections may be referenced by name in ADDR and LOADADDR expressions, 891 // as an empty Section can has a valid VMA and LMA we keep the OutputSection 892 // to maintain the integrity of the other Expression. 893 if (sec.usedInExpression) 894 return false; 895 896 for (BaseCommand *base : sec.sectionCommands) { 897 if (auto cmd = dyn_cast<SymbolAssignment>(base)) 898 // Don't create empty output sections just for unreferenced PROVIDE 899 // symbols. 900 if (cmd->name != "." && !cmd->sym) 901 continue; 902 903 if (!isa<InputSectionDescription>(*base)) 904 return false; 905 } 906 return true; 907 } 908 909 void LinkerScript::adjustSectionsBeforeSorting() { 910 // If the output section contains only symbol assignments, create a 911 // corresponding output section. The issue is what to do with linker script 912 // like ".foo : { symbol = 42; }". One option would be to convert it to 913 // "symbol = 42;". That is, move the symbol out of the empty section 914 // description. That seems to be what bfd does for this simple case. The 915 // problem is that this is not completely general. bfd will give up and 916 // create a dummy section too if there is a ". = . + 1" inside the section 917 // for example. 918 // Given that we want to create the section, we have to worry what impact 919 // it will have on the link. For example, if we just create a section with 920 // 0 for flags, it would change which PT_LOADs are created. 921 // We could remember that particular section is dummy and ignore it in 922 // other parts of the linker, but unfortunately there are quite a few places 923 // that would need to change: 924 // * The program header creation. 925 // * The orphan section placement. 926 // * The address assignment. 927 // The other option is to pick flags that minimize the impact the section 928 // will have on the rest of the linker. That is why we copy the flags from 929 // the previous sections. Only a few flags are needed to keep the impact low. 930 uint64_t flags = SHF_ALLOC; 931 932 for (BaseCommand *&cmd : sectionCommands) { 933 auto *sec = dyn_cast<OutputSection>(cmd); 934 if (!sec) 935 continue; 936 937 // Handle align (e.g. ".foo : ALIGN(16) { ... }"). 938 if (sec->alignExpr) 939 sec->alignment = 940 std::max<uint32_t>(sec->alignment, sec->alignExpr().getValue()); 941 942 // The input section might have been removed (if it was an empty synthetic 943 // section), but we at least know the flags. 944 if (sec->hasInputSections) 945 flags = sec->flags; 946 947 // We do not want to keep any special flags for output section 948 // in case it is empty. 949 bool isEmpty = getInputSections(sec).empty(); 950 if (isEmpty) 951 sec->flags = flags & ((sec->nonAlloc ? 0 : (uint64_t)SHF_ALLOC) | 952 SHF_WRITE | SHF_EXECINSTR); 953 954 if (isEmpty && isDiscardable(*sec)) { 955 sec->markDead(); 956 cmd = nullptr; 957 } else if (!sec->isLive()) { 958 sec->markLive(); 959 } 960 } 961 962 // It is common practice to use very generic linker scripts. So for any 963 // given run some of the output sections in the script will be empty. 964 // We could create corresponding empty output sections, but that would 965 // clutter the output. 966 // We instead remove trivially empty sections. The bfd linker seems even 967 // more aggressive at removing them. 968 llvm::erase_if(sectionCommands, [&](BaseCommand *base) { return !base; }); 969 } 970 971 void LinkerScript::adjustSectionsAfterSorting() { 972 // Try and find an appropriate memory region to assign offsets in. 973 for (BaseCommand *base : sectionCommands) { 974 if (auto *sec = dyn_cast<OutputSection>(base)) { 975 if (!sec->lmaRegionName.empty()) { 976 if (MemoryRegion *m = memoryRegions.lookup(sec->lmaRegionName)) 977 sec->lmaRegion = m; 978 else 979 error("memory region '" + sec->lmaRegionName + "' not declared"); 980 } 981 sec->memRegion = findMemoryRegion(sec); 982 } 983 } 984 985 // If output section command doesn't specify any segments, 986 // and we haven't previously assigned any section to segment, 987 // then we simply assign section to the very first load segment. 988 // Below is an example of such linker script: 989 // PHDRS { seg PT_LOAD; } 990 // SECTIONS { .aaa : { *(.aaa) } } 991 std::vector<StringRef> defPhdrs; 992 auto firstPtLoad = llvm::find_if(phdrsCommands, [](const PhdrsCommand &cmd) { 993 return cmd.type == PT_LOAD; 994 }); 995 if (firstPtLoad != phdrsCommands.end()) 996 defPhdrs.push_back(firstPtLoad->name); 997 998 // Walk the commands and propagate the program headers to commands that don't 999 // explicitly specify them. 1000 for (BaseCommand *base : sectionCommands) { 1001 auto *sec = dyn_cast<OutputSection>(base); 1002 if (!sec) 1003 continue; 1004 1005 if (sec->phdrs.empty()) { 1006 // To match the bfd linker script behaviour, only propagate program 1007 // headers to sections that are allocated. 1008 if (sec->flags & SHF_ALLOC) 1009 sec->phdrs = defPhdrs; 1010 } else { 1011 defPhdrs = sec->phdrs; 1012 } 1013 } 1014 } 1015 1016 static uint64_t computeBase(uint64_t min, bool allocateHeaders) { 1017 // If there is no SECTIONS or if the linkerscript is explicit about program 1018 // headers, do our best to allocate them. 1019 if (!script->hasSectionsCommand || allocateHeaders) 1020 return 0; 1021 // Otherwise only allocate program headers if that would not add a page. 1022 return alignDown(min, config->maxPageSize); 1023 } 1024 1025 // When the SECTIONS command is used, try to find an address for the file and 1026 // program headers output sections, which can be added to the first PT_LOAD 1027 // segment when program headers are created. 1028 // 1029 // We check if the headers fit below the first allocated section. If there isn't 1030 // enough space for these sections, we'll remove them from the PT_LOAD segment, 1031 // and we'll also remove the PT_PHDR segment. 1032 void LinkerScript::allocateHeaders(std::vector<PhdrEntry *> &phdrs) { 1033 uint64_t min = std::numeric_limits<uint64_t>::max(); 1034 for (OutputSection *sec : outputSections) 1035 if (sec->flags & SHF_ALLOC) 1036 min = std::min<uint64_t>(min, sec->addr); 1037 1038 auto it = llvm::find_if( 1039 phdrs, [](const PhdrEntry *e) { return e->p_type == PT_LOAD; }); 1040 if (it == phdrs.end()) 1041 return; 1042 PhdrEntry *firstPTLoad = *it; 1043 1044 bool hasExplicitHeaders = 1045 llvm::any_of(phdrsCommands, [](const PhdrsCommand &cmd) { 1046 return cmd.hasPhdrs || cmd.hasFilehdr; 1047 }); 1048 bool paged = !config->omagic && !config->nmagic; 1049 uint64_t headerSize = getHeaderSize(); 1050 if ((paged || hasExplicitHeaders) && 1051 headerSize <= min - computeBase(min, hasExplicitHeaders)) { 1052 min = alignDown(min - headerSize, config->maxPageSize); 1053 Out::elfHeader->addr = min; 1054 Out::programHeaders->addr = min + Out::elfHeader->size; 1055 return; 1056 } 1057 1058 // Error if we were explicitly asked to allocate headers. 1059 if (hasExplicitHeaders) 1060 error("could not allocate headers"); 1061 1062 Out::elfHeader->ptLoad = nullptr; 1063 Out::programHeaders->ptLoad = nullptr; 1064 firstPTLoad->firstSec = findFirstSection(firstPTLoad); 1065 1066 llvm::erase_if(phdrs, 1067 [](const PhdrEntry *e) { return e->p_type == PT_PHDR; }); 1068 } 1069 1070 LinkerScript::AddressState::AddressState() { 1071 for (auto &mri : script->memoryRegions) { 1072 MemoryRegion *mr = mri.second; 1073 mr->curPos = mr->origin; 1074 } 1075 } 1076 1077 // Here we assign addresses as instructed by linker script SECTIONS 1078 // sub-commands. Doing that allows us to use final VA values, so here 1079 // we also handle rest commands like symbol assignments and ASSERTs. 1080 // Returns a symbol that has changed its section or value, or nullptr if no 1081 // symbol has changed. 1082 const Defined *LinkerScript::assignAddresses() { 1083 if (script->hasSectionsCommand) { 1084 // With a linker script, assignment of addresses to headers is covered by 1085 // allocateHeaders(). 1086 dot = config->imageBase.getValueOr(0); 1087 } else { 1088 // Assign addresses to headers right now. 1089 dot = target->getImageBase(); 1090 Out::elfHeader->addr = dot; 1091 Out::programHeaders->addr = dot + Out::elfHeader->size; 1092 dot += getHeaderSize(); 1093 } 1094 1095 auto deleter = std::make_unique<AddressState>(); 1096 ctx = deleter.get(); 1097 errorOnMissingSection = true; 1098 switchTo(aether); 1099 1100 SymbolAssignmentMap oldValues = getSymbolAssignmentValues(sectionCommands); 1101 for (BaseCommand *base : sectionCommands) { 1102 if (auto *cmd = dyn_cast<SymbolAssignment>(base)) { 1103 cmd->addr = dot; 1104 assignSymbol(cmd, false); 1105 cmd->size = dot - cmd->addr; 1106 continue; 1107 } 1108 assignOffsets(cast<OutputSection>(base)); 1109 } 1110 1111 ctx = nullptr; 1112 return getChangedSymbolAssignment(oldValues); 1113 } 1114 1115 // Creates program headers as instructed by PHDRS linker script command. 1116 std::vector<PhdrEntry *> LinkerScript::createPhdrs() { 1117 std::vector<PhdrEntry *> ret; 1118 1119 // Process PHDRS and FILEHDR keywords because they are not 1120 // real output sections and cannot be added in the following loop. 1121 for (const PhdrsCommand &cmd : phdrsCommands) { 1122 PhdrEntry *phdr = make<PhdrEntry>(cmd.type, cmd.flags ? *cmd.flags : PF_R); 1123 1124 if (cmd.hasFilehdr) 1125 phdr->add(Out::elfHeader); 1126 if (cmd.hasPhdrs) 1127 phdr->add(Out::programHeaders); 1128 1129 if (cmd.lmaExpr) { 1130 phdr->p_paddr = cmd.lmaExpr().getValue(); 1131 phdr->hasLMA = true; 1132 } 1133 ret.push_back(phdr); 1134 } 1135 1136 // Add output sections to program headers. 1137 for (OutputSection *sec : outputSections) { 1138 // Assign headers specified by linker script 1139 for (size_t id : getPhdrIndices(sec)) { 1140 ret[id]->add(sec); 1141 if (!phdrsCommands[id].flags.hasValue()) 1142 ret[id]->p_flags |= sec->getPhdrFlags(); 1143 } 1144 } 1145 return ret; 1146 } 1147 1148 // Returns true if we should emit an .interp section. 1149 // 1150 // We usually do. But if PHDRS commands are given, and 1151 // no PT_INTERP is there, there's no place to emit an 1152 // .interp, so we don't do that in that case. 1153 bool LinkerScript::needsInterpSection() { 1154 if (phdrsCommands.empty()) 1155 return true; 1156 for (PhdrsCommand &cmd : phdrsCommands) 1157 if (cmd.type == PT_INTERP) 1158 return true; 1159 return false; 1160 } 1161 1162 ExprValue LinkerScript::getSymbolValue(StringRef name, const Twine &loc) { 1163 if (name == ".") { 1164 if (ctx) 1165 return {ctx->outSec, false, dot - ctx->outSec->addr, loc}; 1166 error(loc + ": unable to get location counter value"); 1167 return 0; 1168 } 1169 1170 if (Symbol *sym = symtab->find(name)) { 1171 if (auto *ds = dyn_cast<Defined>(sym)) 1172 return {ds->section, false, ds->value, loc}; 1173 if (isa<SharedSymbol>(sym)) 1174 if (!errorOnMissingSection) 1175 return {nullptr, false, 0, loc}; 1176 } 1177 1178 error(loc + ": symbol not found: " + name); 1179 return 0; 1180 } 1181 1182 // Returns the index of the segment named Name. 1183 static Optional<size_t> getPhdrIndex(ArrayRef<PhdrsCommand> vec, 1184 StringRef name) { 1185 for (size_t i = 0; i < vec.size(); ++i) 1186 if (vec[i].name == name) 1187 return i; 1188 return None; 1189 } 1190 1191 // Returns indices of ELF headers containing specific section. Each index is a 1192 // zero based number of ELF header listed within PHDRS {} script block. 1193 std::vector<size_t> LinkerScript::getPhdrIndices(OutputSection *cmd) { 1194 std::vector<size_t> ret; 1195 1196 for (StringRef s : cmd->phdrs) { 1197 if (Optional<size_t> idx = getPhdrIndex(phdrsCommands, s)) 1198 ret.push_back(*idx); 1199 else if (s != "NONE") 1200 error(cmd->location + ": section header '" + s + 1201 "' is not listed in PHDRS"); 1202 } 1203 return ret; 1204 } 1205 1206 } // namespace elf 1207 } // namespace lld 1208