lld/MachO/SymbolTable.cpp

   1 //===- SymbolTable.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 "SymbolTable.h"
  10 #include "ConcatOutputSection.h"
  11 #include "Config.h"
  12 #include "InputFiles.h"
  13 #include "InputSection.h"
  14 #include "Symbols.h"
  15 #include "SyntheticSections.h"
  16 #include "lld/Common/ErrorHandler.h"
  17 #include "lld/Common/Memory.h"
  18
  19 using namespace llvm;
  20 using namespace lld;
  21 using namespace lld::macho;
  22
  23 Symbol *SymbolTable::find(CachedHashStringRef cachedName) {
  24   auto it = symMap.find(cachedName);
  25   if (it == symMap.end())
  26     return nullptr;
  27   return symVector[it->second];
  28 }
  29
  30 std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,
  31                                               const InputFile *file) {
  32   auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
  33
  34   Symbol *sym;
  35   if (!p.second) {
  36     // Name already present in the symbol table.
  37     sym = symVector[p.first->second];
  38   } else {
  39     // Name is a new symbol.
  40     sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
  41     symVector.push_back(sym);
  42   }
  43
  44   sym->isUsedInRegularObj |= !file || isa<ObjFile>(file);
  45   return {sym, p.second};
  46 }
  47
  48 Defined *SymbolTable::addDefined(StringRef name, InputFile *file,
  49                                  InputSection *isec, uint64_t value,
  50                                  uint64_t size, bool isWeakDef,
  51                                  bool isPrivateExtern, bool isThumb,
  52                                  bool isReferencedDynamically, bool noDeadStrip,
  53                                  bool isWeakDefCanBeHidden) {
  54   bool overridesWeakDef = false;
  55   auto [s, wasInserted] = insert(name, file);
  56
  57   assert(!isWeakDef || (isa<BitcodeFile>(file) && !isec) ||
  58          (isa<ObjFile>(file) && file == isec->getFile()));
  59
  60   if (!wasInserted) {
  61     if (auto *defined = dyn_cast<Defined>(s)) {
  62       if (isWeakDef) {
  63         // See further comment in createDefined() in InputFiles.cpp
  64         if (defined->isWeakDef()) {
  65           defined->privateExtern &= isPrivateExtern;
  66           defined->weakDefCanBeHidden &= isWeakDefCanBeHidden;
  67           defined->referencedDynamically |= isReferencedDynamically;
  68           defined->noDeadStrip |= noDeadStrip;
  69         }
  70         // FIXME: Handle this for bitcode files.
  71         if (auto concatIsec = dyn_cast_or_null<ConcatInputSection>(isec))
  72           concatIsec->wasCoalesced = true;
  73         return defined;
  74       }
  75
  76       if (defined->isWeakDef()) {
  77         // FIXME: Handle this for bitcode files.
  78         if (auto concatIsec =
  79                 dyn_cast_or_null<ConcatInputSection>(defined->isec)) {
  80           concatIsec->wasCoalesced = true;
  81           concatIsec->symbols.erase(llvm::find(concatIsec->symbols, defined));
  82         }
  83       } else {
  84         std::string src1 = defined->getSourceLocation();
  85         std::string src2 = isec ? isec->getSourceLocation(value) : "";
  86
  87         std::string message =
  88             "duplicate symbol: " + toString(*defined) + "\n>>> defined in ";
  89         if (!src1.empty())
  90           message += src1 + "\n>>>            ";
  91         message += toString(defined->getFile()) + "\n>>> defined in ";
  92         if (!src2.empty())
  93           message += src2 + "\n>>>            ";
  94         error(message + toString(file));
  95       }
  96
  97     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
  98       overridesWeakDef = !isWeakDef && dysym->isWeakDef();
  99       dysym->unreference();
 100     }
 101     // Defined symbols take priority over other types of symbols, so in case
 102     // of a name conflict, we fall through to the replaceSymbol() call below.
 103   }
 104
 105   // With -flat_namespace, all extern symbols in dylibs are interposable.
 106   // FIXME: Add support for `-interposable` (PR53680).
 107   bool interposable = config->namespaceKind == NamespaceKind::flat &&
 108                       config->outputType != MachO::MH_EXECUTE &&
 109                       !isPrivateExtern;
 110   Defined *defined = replaceSymbol<Defined>(
 111       s, name, file, isec, value, size, isWeakDef, /*isExternal=*/true,
 112       isPrivateExtern, /*includeInSymtab=*/true, isThumb,
 113       isReferencedDynamically, noDeadStrip, overridesWeakDef,
 114       isWeakDefCanBeHidden, interposable);
 115   return defined;
 116 }
 117
 118 Defined *SymbolTable::aliasDefined(Defined *src, StringRef target) {
 119   return addDefined(target, src->getFile(), src->isec, src->value, src->size,
 120                     src->isWeakDef(), src->privateExtern, src->thumb,
 121                     src->referencedDynamically, src->noDeadStrip,
 122                     src->weakDefCanBeHidden);
 123 }
 124
 125 Symbol *SymbolTable::addUndefined(StringRef name, InputFile *file,
 126                                   bool isWeakRef) {
 127   auto [s, wasInserted] = insert(name, file);
 128
 129   RefState refState = isWeakRef ? RefState::Weak : RefState::Strong;
 130
 131   if (wasInserted)
 132     replaceSymbol<Undefined>(s, name, file, refState);
 133   else if (auto *lazy = dyn_cast<LazyArchive>(s))
 134     lazy->fetchArchiveMember();
 135   else if (isa<LazyObject>(s))
 136     extract(*s->getFile(), s->getName());
 137   else if (auto *dynsym = dyn_cast<DylibSymbol>(s))
 138     dynsym->reference(refState);
 139   else if (auto *undefined = dyn_cast<Undefined>(s))
 140     undefined->refState = std::max(undefined->refState, refState);
 141   return s;
 142 }
 143
 144 Symbol *SymbolTable::addCommon(StringRef name, InputFile *file, uint64_t size,
 145                                uint32_t align, bool isPrivateExtern) {
 146   auto [s, wasInserted] = insert(name, file);
 147
 148   if (!wasInserted) {
 149     if (auto *common = dyn_cast<CommonSymbol>(s)) {
 150       if (size < common->size)
 151         return s;
 152     } else if (isa<Defined>(s)) {
 153       return s;
 154     }
 155     // Common symbols take priority over all non-Defined symbols, so in case of
 156     // a name conflict, we fall through to the replaceSymbol() call below.
 157   }
 158
 159   replaceSymbol<CommonSymbol>(s, name, file, size, align, isPrivateExtern);
 160   return s;
 161 }
 162
 163 Symbol *SymbolTable::addDylib(StringRef name, DylibFile *file, bool isWeakDef,
 164                               bool isTlv) {
 165   auto [s, wasInserted] = insert(name, file);
 166
 167   RefState refState = RefState::Unreferenced;
 168   if (!wasInserted) {
 169     if (auto *defined = dyn_cast<Defined>(s)) {
 170       if (isWeakDef && !defined->isWeakDef())
 171         defined->overridesWeakDef = true;
 172     } else if (auto *undefined = dyn_cast<Undefined>(s)) {
 173       refState = undefined->refState;
 174     } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
 175       refState = dysym->getRefState();
 176     }
 177   }
 178
 179   bool isDynamicLookup = file == nullptr;
 180   if (wasInserted || isa<Undefined>(s) ||
 181       (isa<DylibSymbol>(s) &&
 182        ((!isWeakDef && s->isWeakDef()) ||
 183         (!isDynamicLookup && cast<DylibSymbol>(s)->isDynamicLookup())))) {
 184     if (auto *dynsym = dyn_cast<DylibSymbol>(s))
 185       dynsym->unreference();
 186     replaceSymbol<DylibSymbol>(s, file, name, isWeakDef, refState, isTlv);
 187   }
 188
 189   return s;
 190 }
 191
 192 Symbol *SymbolTable::addDynamicLookup(StringRef name) {
 193   return addDylib(name, /*file=*/nullptr, /*isWeakDef=*/false, /*isTlv=*/false);
 194 }
 195
 196 Symbol *SymbolTable::addLazyArchive(StringRef name, ArchiveFile *file,
 197                                     const object::Archive::Symbol &sym) {
 198   auto [s, wasInserted] = insert(name, file);
 199
 200   if (wasInserted) {
 201     replaceSymbol<LazyArchive>(s, file, sym);
 202   } else if (isa<Undefined>(s)) {
 203     file->fetch(sym);
 204   } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
 205     if (dysym->isWeakDef()) {
 206       if (dysym->getRefState() != RefState::Unreferenced)
 207         file->fetch(sym);
 208       else
 209         replaceSymbol<LazyArchive>(s, file, sym);
 210     }
 211   }
 212   return s;
 213 }
 214
 215 Symbol *SymbolTable::addLazyObject(StringRef name, InputFile &file) {
 216   auto [s, wasInserted] = insert(name, &file);
 217
 218   if (wasInserted) {
 219     replaceSymbol<LazyObject>(s, file, name);
 220   } else if (isa<Undefined>(s)) {
 221     extract(file, name);
 222   } else if (auto *dysym = dyn_cast<DylibSymbol>(s)) {
 223     if (dysym->isWeakDef()) {
 224       if (dysym->getRefState() != RefState::Unreferenced)
 225         extract(file, name);
 226       else
 227         replaceSymbol<LazyObject>(s, file, name);
 228     }
 229   }
 230   return s;
 231 }
 232
 233 Defined *SymbolTable::addSynthetic(StringRef name, InputSection *isec,
 234                                    uint64_t value, bool isPrivateExtern,
 235                                    bool includeInSymtab,
 236                                    bool referencedDynamically) {
 237   assert(!isec || !isec->getFile()); // See makeSyntheticInputSection().
 238   Defined *s =
 239       addDefined(name, /*file=*/nullptr, isec, value, /*size=*/0,
 240                  /*isWeakDef=*/false, isPrivateExtern, /*isThumb=*/false,
 241                  referencedDynamically, /*noDeadStrip=*/false,
 242                  /*isWeakDefCanBeHidden=*/false);
 243   s->includeInSymtab = includeInSymtab;
 244   return s;
 245 }
 246
 247 enum class Boundary {
 248   Start,
 249   End,
 250 };
 251
 252 static Defined *createBoundarySymbol(const Undefined &sym) {
 253   return symtab->addSynthetic(
 254       sym.getName(), /*isec=*/nullptr, /*value=*/-1, /*isPrivateExtern=*/true,
 255       /*includeInSymtab=*/false, /*referencedDynamically=*/false);
 256 }
 257
 258 static void handleSectionBoundarySymbol(const Undefined &sym, StringRef segSect,
 259                                         Boundary which) {
 260   StringRef segName, sectName;
 261   std::tie(segName, sectName) = segSect.split('$');
 262
 263   // Attach the symbol to any InputSection that will end up in the right
 264   // OutputSection -- it doesn't matter which one we pick.
 265   // Don't bother looking through inputSections for a matching
 266   // ConcatInputSection -- we need to create ConcatInputSection for
 267   // non-existing sections anyways, and that codepath works even if we should
 268   // already have a ConcatInputSection with the right name.
 269
 270   OutputSection *osec = nullptr;
 271   // This looks for __TEXT,__cstring etc.
 272   for (SyntheticSection *ssec : syntheticSections)
 273     if (ssec->segname == segName && ssec->name == sectName) {
 274       osec = ssec->isec->parent;
 275       break;
 276     }
 277
 278   if (!osec) {
 279     ConcatInputSection *isec = makeSyntheticInputSection(segName, sectName);
 280
 281     // This runs after markLive() and is only called for Undefineds that are
 282     // live. Marking the isec live ensures an OutputSection is created that the
 283     // start/end symbol can refer to.
 284     assert(sym.isLive());
 285     isec->live = true;
 286
 287     // This runs after gatherInputSections(), so need to explicitly set parent
 288     // and add to inputSections.
 289     osec = isec->parent = ConcatOutputSection::getOrCreateForInput(isec);
 290     inputSections.push_back(isec);
 291   }
 292
 293   if (which == Boundary::Start)
 294     osec->sectionStartSymbols.push_back(createBoundarySymbol(sym));
 295   else
 296     osec->sectionEndSymbols.push_back(createBoundarySymbol(sym));
 297 }
 298
 299 static void handleSegmentBoundarySymbol(const Undefined &sym, StringRef segName,
 300                                         Boundary which) {
 301   OutputSegment *seg = getOrCreateOutputSegment(segName);
 302   if (which == Boundary::Start)
 303     seg->segmentStartSymbols.push_back(createBoundarySymbol(sym));
 304   else
 305     seg->segmentEndSymbols.push_back(createBoundarySymbol(sym));
 306 }
 307
 308 // Try to find a definition for an undefined symbol.
 309 // Returns true if a definition was found and no diagnostics are needed.
 310 static bool recoverFromUndefinedSymbol(const Undefined &sym) {
 311   // Handle start/end symbols.
 312   StringRef name = sym.getName();
 313   if (name.consume_front("section$start$")) {
 314     handleSectionBoundarySymbol(sym, name, Boundary::Start);
 315     return true;
 316   }
 317   if (name.consume_front("section$end$")) {
 318     handleSectionBoundarySymbol(sym, name, Boundary::End);
 319     return true;
 320   }
 321   if (name.consume_front("segment$start$")) {
 322     handleSegmentBoundarySymbol(sym, name, Boundary::Start);
 323     return true;
 324   }
 325   if (name.consume_front("segment$end$")) {
 326     handleSegmentBoundarySymbol(sym, name, Boundary::End);
 327     return true;
 328   }
 329
 330   // Leave dtrace symbols, since we will handle them when we do the relocation
 331   if (name.startswith("___dtrace_"))
 332     return true;
 333
 334   // Handle -U.
 335   if (config->explicitDynamicLookups.count(sym.getName())) {
 336     symtab->addDynamicLookup(sym.getName());
 337     return true;
 338   }
 339
 340   // Handle -undefined.
 341   if (config->undefinedSymbolTreatment ==
 342           UndefinedSymbolTreatment::dynamic_lookup ||
 343       config->undefinedSymbolTreatment == UndefinedSymbolTreatment::suppress) {
 344     symtab->addDynamicLookup(sym.getName());
 345     return true;
 346   }
 347
 348   // We do not return true here, as we still need to print diagnostics.
 349   if (config->undefinedSymbolTreatment == UndefinedSymbolTreatment::warning)
 350     symtab->addDynamicLookup(sym.getName());
 351
 352   return false;
 353 }
 354
 355 namespace {
 356 struct UndefinedDiag {
 357   struct SectionAndOffset {
 358     const InputSection *isec;
 359     uint64_t offset;
 360   };
 361
 362   std::vector<SectionAndOffset> codeReferences;
 363   std::vector<std::string> otherReferences;
 364 };
 365
 366 MapVector<const Undefined *, UndefinedDiag> undefs;
 367 }
 368
 369 void macho::reportPendingUndefinedSymbols() {
 370   for (const auto &undef : undefs) {
 371     const UndefinedDiag &locations = undef.second;
 372
 373     std::string message = "undefined symbol";
 374     if (config->archMultiple)
 375       message += (" for arch " + getArchitectureName(config->arch())).str();
 376     message += ": " + toString(*undef.first);
 377
 378     const size_t maxUndefinedReferences = 3;
 379     size_t i = 0;
 380     for (const std::string &loc : locations.otherReferences) {
 381       if (i >= maxUndefinedReferences)
 382         break;
 383       message += "\n>>> referenced by " + loc;
 384       ++i;
 385     }
 386
 387     for (const UndefinedDiag::SectionAndOffset &loc :
 388          locations.codeReferences) {
 389       if (i >= maxUndefinedReferences)
 390         break;
 391       message += "\n>>> referenced by ";
 392       std::string src = loc.isec->getSourceLocation(loc.offset);
 393       if (!src.empty())
 394         message += src + "\n>>>               ";
 395       message += loc.isec->getLocation(loc.offset);
 396       ++i;
 397     }
 398
 399     size_t totalReferences =
 400         locations.otherReferences.size() + locations.codeReferences.size();
 401     if (totalReferences > i)
 402       message +=
 403           ("\n>>> referenced " + Twine(totalReferences - i) + " more times")
 404               .str();
 405
 406     if (config->undefinedSymbolTreatment == UndefinedSymbolTreatment::error)
 407       error(message);
 408     else if (config->undefinedSymbolTreatment ==
 409              UndefinedSymbolTreatment::warning)
 410       warn(message);
 411     else
 412       assert(false &&
 413              "diagnostics make sense for -undefined error|warning only");
 414   }
 415
 416   // This function is called multiple times during execution. Clear the printed
 417   // diagnostics to avoid printing the same things again the next time.
 418   undefs.clear();
 419 }
 420
 421 void macho::treatUndefinedSymbol(const Undefined &sym, StringRef source) {
 422   if (recoverFromUndefinedSymbol(sym))
 423     return;
 424
 425   undefs[&sym].otherReferences.push_back(source.str());
 426 }
 427
 428 void macho::treatUndefinedSymbol(const Undefined &sym, const InputSection *isec,
 429                                  uint64_t offset) {
 430   if (recoverFromUndefinedSymbol(sym))
 431     return;
 432
 433   undefs[&sym].codeReferences.push_back({isec, offset});
 434 }
 435
 436 std::unique_ptr<SymbolTable> macho::symtab;