contrib/llvm-project/lld/ELF/Symbols.cpp

   1 //===- Symbols.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 #include "Symbols.h"
  10 #include "InputFiles.h"
  11 #include "InputSection.h"
  12 #include "OutputSections.h"
  13 #include "SyntheticSections.h"
  14 #include "Target.h"
  15 #include "Writer.h"
  16 #include "lld/Common/ErrorHandler.h"
  17 #include "lld/Common/Strings.h"
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/Support/Path.h"
  20 #include <cstring>
  21
  22 using namespace llvm;
  23 using namespace llvm::object;
  24 using namespace llvm::ELF;
  25
  26 namespace lld {
  27 // Returns a symbol for an error message.
  28 static std::string demangle(StringRef symName) {
  29   if (elf::config->demangle)
  30     return demangleItanium(symName);
  31   return symName;
  32 }
  33
  34 std::string toString(const elf::Symbol &b) { return demangle(b.getName()); }
  35 std::string toELFString(const Archive::Symbol &b) {
  36   return demangle(b.getName());
  37 }
  38
  39 namespace elf {
  40 Defined *ElfSym::bss;
  41 Defined *ElfSym::etext1;
  42 Defined *ElfSym::etext2;
  43 Defined *ElfSym::edata1;
  44 Defined *ElfSym::edata2;
  45 Defined *ElfSym::end1;
  46 Defined *ElfSym::end2;
  47 Defined *ElfSym::globalOffsetTable;
  48 Defined *ElfSym::mipsGp;
  49 Defined *ElfSym::mipsGpDisp;
  50 Defined *ElfSym::mipsLocalGp;
  51 Defined *ElfSym::relaIpltStart;
  52 Defined *ElfSym::relaIpltEnd;
  53 Defined *ElfSym::riscvGlobalPointer;
  54 Defined *ElfSym::tlsModuleBase;
  55
  56 static uint64_t getSymVA(const Symbol &sym, int64_t &addend) {
  57   switch (sym.kind()) {
  58   case Symbol::DefinedKind: {
  59     auto &d = cast<Defined>(sym);
  60     SectionBase *isec = d.section;
  61
  62     // This is an absolute symbol.
  63     if (!isec)
  64       return d.value;
  65
  66     assert(isec != &InputSection::discarded);
  67     isec = isec->repl;
  68
  69     uint64_t offset = d.value;
  70
  71     // An object in an SHF_MERGE section might be referenced via a
  72     // section symbol (as a hack for reducing the number of local
  73     // symbols).
  74     // Depending on the addend, the reference via a section symbol
  75     // refers to a different object in the merge section.
  76     // Since the objects in the merge section are not necessarily
  77     // contiguous in the output, the addend can thus affect the final
  78     // VA in a non-linear way.
  79     // To make this work, we incorporate the addend into the section
  80     // offset (and zero out the addend for later processing) so that
  81     // we find the right object in the section.
  82     if (d.isSection()) {
  83       offset += addend;
  84       addend = 0;
  85     }
  86
  87     // In the typical case, this is actually very simple and boils
  88     // down to adding together 3 numbers:
  89     // 1. The address of the output section.
  90     // 2. The offset of the input section within the output section.
  91     // 3. The offset within the input section (this addition happens
  92     //    inside InputSection::getOffset).
  93     //
  94     // If you understand the data structures involved with this next
  95     // line (and how they get built), then you have a pretty good
  96     // understanding of the linker.
  97     uint64_t va = isec->getVA(offset);
  98
  99     // MIPS relocatable files can mix regular and microMIPS code.
 100     // Linker needs to distinguish such code. To do so microMIPS
 101     // symbols has the `STO_MIPS_MICROMIPS` flag in the `st_other`
 102     // field. Unfortunately, the `MIPS::relocateOne()` method has
 103     // a symbol value only. To pass type of the symbol (regular/microMIPS)
 104     // to that routine as well as other places where we write
 105     // a symbol value as-is (.dynamic section, `Elf_Ehdr::e_entry`
 106     // field etc) do the same trick as compiler uses to mark microMIPS
 107     // for CPU - set the less-significant bit.
 108     if (config->emachine == EM_MIPS && isMicroMips() &&
 109         ((sym.stOther & STO_MIPS_MICROMIPS) || sym.needsPltAddr))
 110       va |= 1;
 111
 112     if (d.isTls() && !config->relocatable) {
 113       // Use the address of the TLS segment's first section rather than the
 114       // segment's address, because segment addresses aren't initialized until
 115       // after sections are finalized. (e.g. Measuring the size of .rela.dyn
 116       // for Android relocation packing requires knowing TLS symbol addresses
 117       // during section finalization.)
 118       if (!Out::tlsPhdr || !Out::tlsPhdr->firstSec)
 119         fatal(toString(d.file) +
 120               " has an STT_TLS symbol but doesn't have an SHF_TLS section");
 121       return va - Out::tlsPhdr->firstSec->addr;
 122     }
 123     return va;
 124   }
 125   case Symbol::SharedKind:
 126   case Symbol::UndefinedKind:
 127     return 0;
 128   case Symbol::LazyArchiveKind:
 129   case Symbol::LazyObjectKind:
 130     assert(sym.isUsedInRegularObj && "lazy symbol reached writer");
 131     return 0;
 132   case Symbol::CommonKind:
 133     llvm_unreachable("common symbol reached writer");
 134   case Symbol::PlaceholderKind:
 135     llvm_unreachable("placeholder symbol reached writer");
 136   }
 137   llvm_unreachable("invalid symbol kind");
 138 }
 139
 140 uint64_t Symbol::getVA(int64_t addend) const {
 141   uint64_t outVA = getSymVA(*this, addend);
 142   return outVA + addend;
 143 }
 144
 145 uint64_t Symbol::getGotVA() const {
 146   if (gotInIgot)
 147     return in.igotPlt->getVA() + getGotPltOffset();
 148   return in.got->getVA() + getGotOffset();
 149 }
 150
 151 uint64_t Symbol::getGotOffset() const { return gotIndex * config->wordsize; }
 152
 153 uint64_t Symbol::getGotPltVA() const {
 154   if (isInIplt)
 155     return in.igotPlt->getVA() + getGotPltOffset();
 156   return in.gotPlt->getVA() + getGotPltOffset();
 157 }
 158
 159 uint64_t Symbol::getGotPltOffset() const {
 160   if (isInIplt)
 161     return pltIndex * config->wordsize;
 162   return (pltIndex + target->gotPltHeaderEntriesNum) * config->wordsize;
 163 }
 164
 165 uint64_t Symbol::getPPC64LongBranchOffset() const {
 166   assert(ppc64BranchltIndex != 0xffff);
 167   return ppc64BranchltIndex * config->wordsize;
 168 }
 169
 170 uint64_t Symbol::getPltVA() const {
 171   PltSection *plt = isInIplt ? in.iplt : in.plt;
 172   uint64_t outVA =
 173       plt->getVA() + plt->headerSize + pltIndex * target->pltEntrySize;
 174   // While linking microMIPS code PLT code are always microMIPS
 175   // code. Set the less-significant bit to track that fact.
 176   // See detailed comment in the `getSymVA` function.
 177   if (config->emachine == EM_MIPS && isMicroMips())
 178     outVA |= 1;
 179   return outVA;
 180 }
 181
 182 uint64_t Symbol::getPPC64LongBranchTableVA() const {
 183   assert(ppc64BranchltIndex != 0xffff);
 184   return in.ppc64LongBranchTarget->getVA() +
 185          ppc64BranchltIndex * config->wordsize;
 186 }
 187
 188 uint64_t Symbol::getSize() const {
 189   if (const auto *dr = dyn_cast<Defined>(this))
 190     return dr->size;
 191   return cast<SharedSymbol>(this)->size;
 192 }
 193
 194 OutputSection *Symbol::getOutputSection() const {
 195   if (auto *s = dyn_cast<Defined>(this)) {
 196     if (auto *sec = s->section)
 197       return sec->repl->getOutputSection();
 198     return nullptr;
 199   }
 200   return nullptr;
 201 }
 202
 203 // If a symbol name contains '@', the characters after that is
 204 // a symbol version name. This function parses that.
 205 void Symbol::parseSymbolVersion() {
 206   StringRef s = getName();
 207   size_t pos = s.find('@');
 208   if (pos == 0 || pos == StringRef::npos)
 209     return;
 210   StringRef verstr = s.substr(pos + 1);
 211   if (verstr.empty())
 212     return;
 213
 214   // Truncate the symbol name so that it doesn't include the version string.
 215   nameSize = pos;
 216
 217   // If this is not in this DSO, it is not a definition.
 218   if (!isDefined())
 219     return;
 220
 221   // '@@' in a symbol name means the default version.
 222   // It is usually the most recent one.
 223   bool isDefault = (verstr[0] == '@');
 224   if (isDefault)
 225     verstr = verstr.substr(1);
 226
 227   for (const VersionDefinition &ver : namedVersionDefs()) {
 228     if (ver.name != verstr)
 229       continue;
 230
 231     if (isDefault)
 232       versionId = ver.id;
 233     else
 234       versionId = ver.id | VERSYM_HIDDEN;
 235     return;
 236   }
 237
 238   // It is an error if the specified version is not defined.
 239   // Usually version script is not provided when linking executable,
 240   // but we may still want to override a versioned symbol from DSO,
 241   // so we do not report error in this case. We also do not error
 242   // if the symbol has a local version as it won't be in the dynamic
 243   // symbol table.
 244   if (config->shared && versionId != VER_NDX_LOCAL)
 245     error(toString(file) + ": symbol " + s + " has undefined version " +
 246           verstr);
 247 }
 248
 249 void Symbol::fetch() const {
 250   if (auto *sym = dyn_cast<LazyArchive>(this)) {
 251     cast<ArchiveFile>(sym->file)->fetch(sym->sym);
 252     return;
 253   }
 254
 255   if (auto *sym = dyn_cast<LazyObject>(this)) {
 256     dyn_cast<LazyObjFile>(sym->file)->fetch();
 257     return;
 258   }
 259
 260   llvm_unreachable("Symbol::fetch() is called on a non-lazy symbol");
 261 }
 262
 263 MemoryBufferRef LazyArchive::getMemberBuffer() {
 264   Archive::Child c =
 265       CHECK(sym.getMember(),
 266             "could not get the member for symbol " + toELFString(sym));
 267
 268   return CHECK(c.getMemoryBufferRef(),
 269                "could not get the buffer for the member defining symbol " +
 270                    toELFString(sym));
 271 }
 272
 273 uint8_t Symbol::computeBinding() const {
 274   if (config->relocatable)
 275     return binding;
 276   if ((visibility != STV_DEFAULT && visibility != STV_PROTECTED) ||
 277       versionId == VER_NDX_LOCAL)
 278     return STB_LOCAL;
 279   if (!config->gnuUnique && binding == STB_GNU_UNIQUE)
 280     return STB_GLOBAL;
 281   return binding;
 282 }
 283
 284 bool Symbol::includeInDynsym() const {
 285   if (!config->hasDynSymTab)
 286     return false;
 287   if (computeBinding() == STB_LOCAL)
 288     return false;
 289
 290   // If a PIE binary was not linked against any shared libraries, then we can
 291   // safely drop weak undef symbols from .dynsym.
 292   if (isUndefWeak() && config->pie && sharedFiles.empty())
 293     return false;
 294
 295   return isUndefined() || isShared() || exportDynamic || inDynamicList;
 296 }
 297
 298 // Print out a log message for --trace-symbol.
 299 void printTraceSymbol(const Symbol *sym) {
 300   std::string s;
 301   if (sym->isUndefined())
 302     s = ": reference to ";
 303   else if (sym->isLazy())
 304     s = ": lazy definition of ";
 305   else if (sym->isShared())
 306     s = ": shared definition of ";
 307   else if (sym->isCommon())
 308     s = ": common definition of ";
 309   else
 310     s = ": definition of ";
 311
 312   message(toString(sym->file) + s + sym->getName());
 313 }
 314
 315 void maybeWarnUnorderableSymbol(const Symbol *sym) {
 316   if (!config->warnSymbolOrdering)
 317     return;
 318
 319   // If UnresolvedPolicy::Ignore is used, no "undefined symbol" error/warning
 320   // is emitted. It makes sense to not warn on undefined symbols.
 321   //
 322   // Note, ld.bfd --symbol-ordering-file= does not warn on undefined symbols,
 323   // but we don't have to be compatible here.
 324   if (sym->isUndefined() &&
 325       config->unresolvedSymbols == UnresolvedPolicy::Ignore)
 326     return;
 327
 328   const InputFile *file = sym->file;
 329   auto *d = dyn_cast<Defined>(sym);
 330
 331   auto report = [&](StringRef s) { warn(toString(file) + s + sym->getName()); };
 332
 333   if (sym->isUndefined())
 334     report(": unable to order undefined symbol: ");
 335   else if (sym->isShared())
 336     report(": unable to order shared symbol: ");
 337   else if (d && !d->section)
 338     report(": unable to order absolute symbol: ");
 339   else if (d && isa<OutputSection>(d->section))
 340     report(": unable to order synthetic symbol: ");
 341   else if (d && !d->section->repl->isLive())
 342     report(": unable to order discarded symbol: ");
 343 }
 344
 345 static uint8_t getMinVisibility(uint8_t va, uint8_t vb) {
 346   if (va == STV_DEFAULT)
 347     return vb;
 348   if (vb == STV_DEFAULT)
 349     return va;
 350   return std::min(va, vb);
 351 }
 352
 353 // Merge symbol properties.
 354 //
 355 // When we have many symbols of the same name, we choose one of them,
 356 // and that's the result of symbol resolution. However, symbols that
 357 // were not chosen still affect some symbol properties.
 358 void Symbol::mergeProperties(const Symbol &other) {
 359   if (other.exportDynamic)
 360     exportDynamic = true;
 361   if (other.isUsedInRegularObj)
 362     isUsedInRegularObj = true;
 363
 364   // DSO symbols do not affect visibility in the output.
 365   if (!other.isShared())
 366     visibility = getMinVisibility(visibility, other.visibility);
 367 }
 368
 369 void Symbol::resolve(const Symbol &other) {
 370   mergeProperties(other);
 371
 372   if (isPlaceholder()) {
 373     replace(other);
 374     return;
 375   }
 376
 377   switch (other.kind()) {
 378   case Symbol::UndefinedKind:
 379     resolveUndefined(cast<Undefined>(other));
 380     break;
 381   case Symbol::CommonKind:
 382     resolveCommon(cast<CommonSymbol>(other));
 383     break;
 384   case Symbol::DefinedKind:
 385     resolveDefined(cast<Defined>(other));
 386     break;
 387   case Symbol::LazyArchiveKind:
 388     resolveLazy(cast<LazyArchive>(other));
 389     break;
 390   case Symbol::LazyObjectKind:
 391     resolveLazy(cast<LazyObject>(other));
 392     break;
 393   case Symbol::SharedKind:
 394     resolveShared(cast<SharedSymbol>(other));
 395     break;
 396   case Symbol::PlaceholderKind:
 397     llvm_unreachable("bad symbol kind");
 398   }
 399 }
 400
 401 void Symbol::resolveUndefined(const Undefined &other) {
 402   // An undefined symbol with non default visibility must be satisfied
 403   // in the same DSO.
 404   //
 405   // If this is a non-weak defined symbol in a discarded section, override the
 406   // existing undefined symbol for better error message later.
 407   if ((isShared() && other.visibility != STV_DEFAULT) ||
 408       (isUndefined() && other.binding != STB_WEAK && other.discardedSecIdx)) {
 409     replace(other);
 410     return;
 411   }
 412
 413   if (traced)
 414     printTraceSymbol(&other);
 415
 416   if (isLazy()) {
 417     // An undefined weak will not fetch archive members. See comment on Lazy in
 418     // Symbols.h for the details.
 419     if (other.binding == STB_WEAK) {
 420       binding = STB_WEAK;
 421       type = other.type;
 422       return;
 423     }
 424
 425     // Do extra check for --warn-backrefs.
 426     //
 427     // --warn-backrefs is an option to prevent an undefined reference from
 428     // fetching an archive member written earlier in the command line. It can be
 429     // used to keep compatibility with GNU linkers to some degree.
 430     // I'll explain the feature and why you may find it useful in this comment.
 431     //
 432     // lld's symbol resolution semantics is more relaxed than traditional Unix
 433     // linkers. For example,
 434     //
 435     //   ld.lld foo.a bar.o
 436     //
 437     // succeeds even if bar.o contains an undefined symbol that has to be
 438     // resolved by some object file in foo.a. Traditional Unix linkers don't
 439     // allow this kind of backward reference, as they visit each file only once
 440     // from left to right in the command line while resolving all undefined
 441     // symbols at the moment of visiting.
 442     //
 443     // In the above case, since there's no undefined symbol when a linker visits
 444     // foo.a, no files are pulled out from foo.a, and because the linker forgets
 445     // about foo.a after visiting, it can't resolve undefined symbols in bar.o
 446     // that could have been resolved otherwise.
 447     //
 448     // That lld accepts more relaxed form means that (besides it'd make more
 449     // sense) you can accidentally write a command line or a build file that
 450     // works only with lld, even if you have a plan to distribute it to wider
 451     // users who may be using GNU linkers. With --warn-backrefs, you can detect
 452     // a library order that doesn't work with other Unix linkers.
 453     //
 454     // The option is also useful to detect cyclic dependencies between static
 455     // archives. Again, lld accepts
 456     //
 457     //   ld.lld foo.a bar.a
 458     //
 459     // even if foo.a and bar.a depend on each other. With --warn-backrefs, it is
 460     // handled as an error.
 461     //
 462     // Here is how the option works. We assign a group ID to each file. A file
 463     // with a smaller group ID can pull out object files from an archive file
 464     // with an equal or greater group ID. Otherwise, it is a reverse dependency
 465     // and an error.
 466     //
 467     // A file outside --{start,end}-group gets a fresh ID when instantiated. All
 468     // files within the same --{start,end}-group get the same group ID. E.g.
 469     //
 470     //   ld.lld A B --start-group C D --end-group E
 471     //
 472     // A forms group 0. B form group 1. C and D (including their member object
 473     // files) form group 2. E forms group 3. I think that you can see how this
 474     // group assignment rule simulates the traditional linker's semantics.
 475     bool backref = config->warnBackrefs && other.file &&
 476                    file->groupId < other.file->groupId;
 477     fetch();
 478
 479     // We don't report backward references to weak symbols as they can be
 480     // overridden later.
 481     if (backref && !isWeak())
 482       warn("backward reference detected: " + other.getName() + " in " +
 483            toString(other.file) + " refers to " + toString(file));
 484     return;
 485   }
 486
 487   // Undefined symbols in a SharedFile do not change the binding.
 488   if (dyn_cast_or_null<SharedFile>(other.file))
 489     return;
 490
 491   if (isUndefined() || isShared()) {
 492     // The binding will be weak if there is at least one reference and all are
 493     // weak. The binding has one opportunity to change to weak: if the first
 494     // reference is weak.
 495     if (other.binding != STB_WEAK || !referenced)
 496       binding = other.binding;
 497     referenced = true;
 498   }
 499 }
 500
 501 // Using .symver foo,foo@@VER unfortunately creates two symbols: foo and
 502 // foo@@VER. We want to effectively ignore foo, so give precedence to
 503 // foo@@VER.
 504 // FIXME: If users can transition to using
 505 // .symver foo,foo@@@VER
 506 // we can delete this hack.
 507 static int compareVersion(StringRef a, StringRef b) {
 508   bool x = a.contains("@@");
 509   bool y = b.contains("@@");
 510   if (!x && y)
 511     return 1;
 512   if (x && !y)
 513     return -1;
 514   return 0;
 515 }
 516
 517 // Compare two symbols. Return 1 if the new symbol should win, -1 if
 518 // the new symbol should lose, or 0 if there is a conflict.
 519 int Symbol::compare(const Symbol *other) const {
 520   assert(other->isDefined() || other->isCommon());
 521
 522   if (!isDefined() && !isCommon())
 523     return 1;
 524
 525   if (int cmp = compareVersion(getName(), other->getName()))
 526     return cmp;
 527
 528   if (other->isWeak())
 529     return -1;
 530
 531   if (isWeak())
 532     return 1;
 533
 534   if (isCommon() && other->isCommon()) {
 535     if (config->warnCommon)
 536       warn("multiple common of " + getName());
 537     return 0;
 538   }
 539
 540   if (isCommon()) {
 541     if (config->warnCommon)
 542       warn("common " + getName() + " is overridden");
 543     return 1;
 544   }
 545
 546   if (other->isCommon()) {
 547     if (config->warnCommon)
 548       warn("common " + getName() + " is overridden");
 549     return -1;
 550   }
 551
 552   auto *oldSym = cast<Defined>(this);
 553   auto *newSym = cast<Defined>(other);
 554
 555   if (dyn_cast_or_null<BitcodeFile>(other->file))
 556     return 0;
 557
 558   if (!oldSym->section && !newSym->section && oldSym->value == newSym->value &&
 559       newSym->binding == STB_GLOBAL)
 560     return -1;
 561
 562   return 0;
 563 }
 564
 565 static void reportDuplicate(Symbol *sym, InputFile *newFile,
 566                             InputSectionBase *errSec, uint64_t errOffset) {
 567   if (config->allowMultipleDefinition)
 568     return;
 569
 570   Defined *d = cast<Defined>(sym);
 571   if (!d->section || !errSec) {
 572     error("duplicate symbol: " + toString(*sym) + "\n>>> defined in " +
 573           toString(sym->file) + "\n>>> defined in " + toString(newFile));
 574     return;
 575   }
 576
 577   // Construct and print an error message in the form of:
 578   //
 579   //   ld.lld: error: duplicate symbol: foo
 580   //   >>> defined at bar.c:30
 581   //   >>>            bar.o (/home/alice/src/bar.o)
 582   //   >>> defined at baz.c:563
 583   //   >>>            baz.o in archive libbaz.a
 584   auto *sec1 = cast<InputSectionBase>(d->section);
 585   std::string src1 = sec1->getSrcMsg(*sym, d->value);
 586   std::string obj1 = sec1->getObjMsg(d->value);
 587   std::string src2 = errSec->getSrcMsg(*sym, errOffset);
 588   std::string obj2 = errSec->getObjMsg(errOffset);
 589
 590   std::string msg = "duplicate symbol: " + toString(*sym) + "\n>>> defined at ";
 591   if (!src1.empty())
 592     msg += src1 + "\n>>>            ";
 593   msg += obj1 + "\n>>> defined at ";
 594   if (!src2.empty())
 595     msg += src2 + "\n>>>            ";
 596   msg += obj2;
 597   error(msg);
 598 }
 599
 600 void Symbol::resolveCommon(const CommonSymbol &other) {
 601   int cmp = compare(&other);
 602   if (cmp < 0)
 603     return;
 604
 605   if (cmp > 0) {
 606     replace(other);
 607     return;
 608   }
 609
 610   CommonSymbol *oldSym = cast<CommonSymbol>(this);
 611
 612   oldSym->alignment = std::max(oldSym->alignment, other.alignment);
 613   if (oldSym->size < other.size) {
 614     oldSym->file = other.file;
 615     oldSym->size = other.size;
 616   }
 617 }
 618
 619 void Symbol::resolveDefined(const Defined &other) {
 620   int cmp = compare(&other);
 621   if (cmp > 0)
 622     replace(other);
 623   else if (cmp == 0)
 624     reportDuplicate(this, other.file,
 625                     dyn_cast_or_null<InputSectionBase>(other.section),
 626                     other.value);
 627 }
 628
 629 template <class LazyT> void Symbol::resolveLazy(const LazyT &other) {
 630   if (!isUndefined())
 631     return;
 632
 633   // An undefined weak will not fetch archive members. See comment on Lazy in
 634   // Symbols.h for the details.
 635   if (isWeak()) {
 636     uint8_t ty = type;
 637     replace(other);
 638     type = ty;
 639     binding = STB_WEAK;
 640     return;
 641   }
 642
 643   other.fetch();
 644 }
 645
 646 void Symbol::resolveShared(const SharedSymbol &other) {
 647   if (visibility == STV_DEFAULT && (isUndefined() || isLazy())) {
 648     // An undefined symbol with non default visibility must be satisfied
 649     // in the same DSO.
 650     uint8_t bind = binding;
 651     replace(other);
 652     binding = bind;
 653     referenced = true;
 654   }
 655 }
 656
 657 } // namespace elf
 658 } // namespace lld