[lld-macho] Add support for N_INDR symbols

[int3]

Summary

This is similar to the -alias CLI option, but it gives finer-grained
control in that it allows the aliased symbols to be treated as private
externs.

While working on this, I realized that our -alias handling did not
cover the cases where the aliased symbol is a common or dylib symbol,
nor the case where we have an undefined that gets treated specially and
converted to a defined later on. My N_INDR handling neglects this too
for now; I've added checks and TODO messages for these.

N_INDR symbols cropped up as part of our attempt to link swift-stdlib.

[int3]

lld/MachO/Driver.cpp

1204

I very mildly prefer not using continue to break out of just one level of nesting, but happy to change it back if anyone prefers the original

[int3]

tweak comment

[thakis]

lld/MachO/Driver.cpp

1216

This feels a bit inelegant. Conceptually, an alias and its target could be two map entries pointing at the same symbol – if it weren't for the fact that the alias can have more restrictive visibility :/

lld/MachO/SymbolTable.h

46

nit: isPrivateExtern for consistency with previous method?

lld/test/MachO/symbol-aliases.s

44

Do you have a test for an extern alias to a local or a private extern target?

[thakis]

Oh, maybe worth adding an alias to the dead stripping test (to make sure alias insertion happens before dead stripping).

[thevinster]

Overall, lgtm. Thanks!

lld/MachO/Driver.cpp

1216

If we have an object file that uses aliases and we also specify -alias from the command line, the object file alias will replace the one from the command line. Conceptually speaking, should it be the other way around? I haven't tested this explicitly but am interested to know this result.

lld/MachO/SymbolTable.cpp

120

Does this mean that both the alias and aliased symbol can differ in symbol visibility? If so, might be worth adding a test for it if it's expected behavior.

[int3]

lld/MachO/Driver.cpp

1216

agreed heh

1216

ooh, good question. let me add that test case

lld/MachO/SymbolTable.cpp

120

I'm not sure I understand the question. Are you asking if they can have visibilities that differ from each other? Yes, but that is already being tested...

lld/MachO/SymbolTable.h

46

sure. I was thinking that isPrivateExtern sounded like it could apply to either the src or target, whereas makePrivateExtern is more clearly something that will be applied to the newly-created symbol. But consistency is good too

lld/test/MachO/symbol-aliases.s

44

I'll add a test for a private extern target. AFAICT, MC won't generate aliases to locals (it will just refer to the aliased symbol itself), so that case can't / doesn't need to be tested.

[thevinster]

lld/MachO/SymbolTable.cpp

120

Whoops, must've missed that. I guess it would be nice to also test a global alias to a private extern symbol too just to make sure we test all combinations. But I see, thakis@ already commented that as well.

[int3]

So, as per Vincent's suggestion, I wrote some tests to see if/when aliases could overwrite other aliases. And I realize that I had gotten it wrong... in fact, alias symbols are always treated as strongly-defined symbols, even if the aliased symbol is weak. I.e. if we have two definitions of _a, either one (or both) an alias to a weak def _b, we will still encounter a dup symbol error for the two _as.

That said, I'm not sure the implementation complexity of emulating this behavior is worth it... we would essentially have to put AliasSymbols into the global SymbolTable. Which means that every addDefined, addLazy etc call will now have to correctly handling the AliasSymbol case. *Or* we could, instead of creating a separate AliasSymbol class, instead make Defineds able to represent aliases. We could have a Defined::isAlias bit, and use that to make a tagged union out of Defined::isec; that same slot can be used to point to a StringRef of the aliased name.

The former is tedious and the latter is frankly kind of ugly. Given that we are merely being more permissible than ld64 with our current "aliases can override" behavior, I'm not sure this extra work is worth it -- any alias-using programs linkable with ld64 should be linkable with LLD under the current semantics.

If @thakis @oontvoo etc don't mind I'm just going to document this as another behavior difference in our docs.

lld/test/MachO/symbol-aliases.s

25–32

Oh, maybe worth adding an alias to the dead stripping test (to make sure alias insertion happens before dead stripping).

@thakis I think these lines already cover that case

74

I messed up here. I thought that this second definition of _extern_alias_to_weak was demonstrating that we could have two separate aliases of the same name w/o a dup symbol error, but actually MC doesn't even generate an alias at all here since _weak is defined in the same file -- references to _extern_alias_to_weak are automatically emitted as references to _weak

[int3]

(hit enter too early last message, please see final edits if you got a truncated comment via email)

[int3]

update

[int3]

I'm just going to document this as another behavior difference in our docs.

This is done. Will wait a bit for feedback before landing :)

[thakis]

If @thakis @oontvoo etc don't mind I'm just going to document this as another behavior difference in our docs.

I don't have an opinion on this. Seems fine.

[thakis]

As far as I can tell, this breaks tests everywhere (eg http://45.33.8.238/linux/86581/step_11.txt)

Please take a look and revert for now if it takes a while to fix.

(Also, please run tests locally before commiting)

[thakis]

reverted in c28f4e3f047affece3ebb475bbc13de6096710c3 for now

[int3]

Sorry, I do run tests locally, just not always with assertions enabled...

I'm not sure I understand the purpose of the assertion tbh -- @thakis you introduced it in D102076. We're triggering it now because alias symbols can be weak + can be defined with a different InputFile than the section they ultimately belong to. Can we just remove the assert?

[int3]

I don't think there's a way to preserve the intent of the assert without adding another parameter to addDefined to indicate whether we are creating an alias or not. Will remove the assert

lld/MachO/Driver.cpp

static void referenceStubBinder() {
   // dyld_stub_binder doesn't exist in case it is actually needed.
   symtab->addUndefined("dyld_stub_binder", /*file=*/nullptr, /*isWeak=*/false);
 }
 
 static void createAliases() {
   for (const auto &pair : config->aliasedSymbols) {
     if (const auto &sym = symtab->find(pair.first)) {
       if (const auto &defined = dyn_cast<Defined>(sym)) {
-        symtab->aliasDefined(defined, pair.second);
-        continue;
-      }
+        symtab->aliasDefined(defined, pair.second, defined->getFile());
+      } else {
+        error("TODO: support aliasing to symbols of kind " +
+              Twine(sym->kind()));
       }
-
+    } else {
       warn("undefined base symbol '" + pair.first + "' for alias '" +
            pair.second + "'\n");
     }
   }
 
+  for (const InputFile *file : inputFiles) {
+    if (auto *objFile = dyn_cast<ObjFile>(file)) {
+      for (const AliasSymbol *alias : objFile->aliases) {
+        if (const auto &aliased = symtab->find(alias->getAliasedName())) {
+          if (const auto &defined = dyn_cast<Defined>(aliased)) {
+            symtab->aliasDefined(defined, alias->getName(), alias->getFile(),
+                                 alias->privateExtern);
+          } else {
+            // Common, dylib, and undefined symbols are all valid alias
+            // referents (undefineds can become valid Defined symbols later on
+            // in the link.)
+            error("TODO: support aliasing to symbols of kind " +
+                  Twine(aliased->kind()));
+          }
+        } else {
+          // This shouldn't happen since MC generates undefined symbols to
+          // represent the alias referents. Thus we fatal() instead of just
+          // warning here.
+          fatal("unable to find alias referent " + alias->getAliasedName() +
+                " for " + alias->getName());
+        }
+      }
+    }
+  }
+}
+
 static void handleExplicitExports() {
   if (config->hasExplicitExports) {
     parallelForEach(symtab->getSymbols(), [](Symbol *sym) {
       if (auto *defined = dyn_cast<Defined>(sym)) {
         StringRef symbolName = defined->getName();
         if (config->exportedSymbols.match(symbolName)) {
           if (defined->privateExtern) {
             if (defined->weakDefCanBeHidden) {

lld/MachO/InputFiles.h

 
 namespace lld {
 namespace macho {
 
 struct PlatformInfo;
 class ConcatInputSection;
 class Symbol;
 class Defined;
+class AliasSymbol;
 struct Reloc;
 enum class RefState : uint8_t;
 
 // If --reproduce option is given, all input files are written
 // to this tar archive.
 extern std::unique_ptr<llvm::TarWriter> tar;
 
 // If .subsections_via_symbols is set, each InputSection will be split along
public:
   std::unique_ptr<lld::DWARFCache> dwarfCache;
   Section *addrSigSection = nullptr;
   const uint32_t modTime;
   bool forceHidden;
   std::vector<ConcatInputSection *> debugSections;
   std::vector<CallGraphEntry> callGraph;
   llvm::DenseMap<ConcatInputSection *, FDE> fdes;
   std::vector<OptimizationHint> optimizationHints;
+  std::vector<AliasSymbol *> aliases;
 
 private:
   llvm::once_flag initDwarf;
   template <class LP> void parseLazy();
   template <class SectionHeader> void parseSections(ArrayRef<SectionHeader>);
   template <class LP>
   void parseSymbols(ArrayRef<typename LP::section> sectionHeaders,
                     ArrayRef<typename LP::nlist> nList, const char *strtab,
                     bool subsectionsViaSymbols);
   template <class NList>
-  Symbol *parseNonSectionSymbol(const NList &sym, StringRef name);
+  Symbol *parseNonSectionSymbol(const NList &sym, const char *strtab);
   template <class SectionHeader>
   void parseRelocations(ArrayRef<SectionHeader> sectionHeaders,
                         const SectionHeader &, Section &);
   void parseDebugInfo();
   void parseOptimizationHints(ArrayRef<uint8_t> data);
   void splitEhFrames(ArrayRef<uint8_t> dataArr, Section &ehFrameSection);
   void registerCompactUnwind(Section &compactUnwindSection);
   void registerEhFrames(Section &ehFrameSection);

lld/MachO/InputFiles.cpp

return make<Defined>(name, file, nullptr, sym.n_value, /*size=*/0,
                        /*isExternal=*/false, /*isPrivateExtern=*/false,
                        /*includeInSymtab=*/true, sym.n_desc & N_ARM_THUMB_DEF,
                        /*isReferencedDynamically=*/false,
                        sym.n_desc & N_NO_DEAD_STRIP);
 }
 
 template <class NList>
 macho::Symbol *ObjFile::parseNonSectionSymbol(const NList &sym,
-                                              StringRef name) {
+                                              const char *strtab) {
+  StringRef name = StringRef(strtab + sym.n_strx);
   uint8_t type = sym.n_type & N_TYPE;
   bool isPrivateExtern = sym.n_type & N_PEXT || forceHidden;
   switch (type) {
   case N_UNDF:
     return sym.n_value == 0
                ? symtab->addUndefined(name, this, sym.n_desc & N_WEAK_REF)
                : symtab->addCommon(name, this, sym.n_value,
                                    1 << GET_COMM_ALIGN(sym.n_desc),
                                    isPrivateExtern);
   case N_ABS:
     return createAbsolute(sym, this, name, forceHidden);
+  case N_INDR: {
+    // Not much point in making local aliases -- relocs in the current file can
+    // just refer to the actual symbol itself. ld64 ignores these symbols too.
+    if (!(sym.n_type & N_EXT))
+      return nullptr;
+    StringRef aliasedName = StringRef(strtab + sym.n_value);
+    // isPrivateExtern is the only symbol flag that has an impact on the final
+    // aliased symbol.
+    auto alias = make<AliasSymbol>(this, name, aliasedName, isPrivateExtern);
+    aliases.push_back(alias);
+    return alias;
+  }
   case N_PBUD:
-  case N_INDR:
-    error("TODO: support symbols of type " + std::to_string(type));
+    error("TODO: support symbols of type N_PBUD");
     return nullptr;
   case N_SECT:
     llvm_unreachable(
         "N_SECT symbols should not be passed to parseNonSectionSymbol");
   default:
     llvm_unreachable("invalid symbol type");
   }
 }
if ((sym.n_type & N_TYPE) == N_SECT) {
       Subsections &subsections = sections[sym.n_sect - 1]->subsections;
       // parseSections() may have chosen not to parse this section.
       if (subsections.empty())
         continue;
       symbolsBySection[sym.n_sect - 1].push_back(i);
     } else if (isUndef(sym)) {
       undefineds.push_back(i);
     } else {
-      symbols[i] = parseNonSectionSymbol(sym, StringRef(strtab + sym.n_strx));
+      symbols[i] = parseNonSectionSymbol(sym, strtab);
     }
   }
 
   for (size_t i = 0; i < sections.size(); ++i) {
     Subsections &subsections = sections[i]->subsections;
     if (subsections.empty())
       continue;
     std::vector<uint32_t> &symbolIndices = symbolsBySection[i];
void ObjFile::parseSymbols(ArrayRef<typename LP::section> sectionHeaders,
   }
 
   // Undefined symbols can trigger recursive fetch from Archives due to
   // LazySymbols. Process defined symbols first so that the relative order
   // between a defined symbol and an undefined symbol does not change the
   // symbol resolution behavior. In addition, a set of interconnected symbols
   // will all be resolved to the same file, instead of being resolved to
   // different files.
-  for (unsigned i : undefineds) {
-    const NList &sym = nList[i];
-    StringRef name = strtab + sym.n_strx;
-    symbols[i] = parseNonSectionSymbol(sym, name);
-  }
+  for (unsigned i : undefineds)
+    symbols[i] = parseNonSectionSymbol(nList[i], strtab);
 }
 
 OpaqueFile::OpaqueFile(MemoryBufferRef mb, StringRef segName,
                        StringRef sectName)
     : InputFile(OpaqueKind, mb) {
   const auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   ArrayRef<uint8_t> data = {buf, mb.getBufferSize()};
   sections.push_back(make<Section>(/*file=*/this, segName.take_front(16),

lld/MachO/SymbolTable.h

 class SymbolTable {
 public:
   Defined *addDefined(StringRef name, InputFile *, InputSection *,
                       uint64_t value, uint64_t size, bool isWeakDef,
                       bool isPrivateExtern, bool isThumb,
                       bool isReferencedDynamically, bool noDeadStrip,
                       bool isWeakDefCanBeHidden);
 
-  Defined *aliasDefined(Defined *src, StringRef target);
+  Defined *aliasDefined(Defined *src, StringRef target, InputFile *newFile,
+                        bool makePrivateExtern = false);
 
   Symbol *addUndefined(StringRef name, InputFile *, bool isWeakRef);
 
   Symbol *addCommon(StringRef name, InputFile *, uint64_t size, uint32_t align,
                     bool isPrivateExtern);
 
   Symbol *addDylib(StringRef name, DylibFile *file, bool isWeakDef, bool isTlv);
   Symbol *addDynamicLookup(StringRef name);

lld/MachO/SymbolTable.cpp

Defined *SymbolTable::addDefined(StringRef name, InputFile *file,
   Defined *defined = replaceSymbol<Defined>(
       s, name, file, isec, value, size, isWeakDef, /*isExternal=*/true,
       isPrivateExtern, /*includeInSymtab=*/true, isThumb,
       isReferencedDynamically, noDeadStrip, overridesWeakDef,
       isWeakDefCanBeHidden, interposable);
   return defined;
 }
 
-Defined *SymbolTable::aliasDefined(Defined *src, StringRef target) {
-  return addDefined(target, src->getFile(), src->isec, src->value, src->size,
-                    src->isWeakDef(), src->privateExtern, src->thumb,
+Defined *SymbolTable::aliasDefined(Defined *src, StringRef target,
+                                   InputFile *newFile, bool makePrivateExtern) {
+  bool isPrivateExtern = makePrivateExtern || src->privateExtern;
+  return addDefined(target, newFile, src->isec, src->value, src->size,
+                    src->isWeakDef(), isPrivateExtern, src->thumb,
                     src->referencedDynamically, src->noDeadStrip,
                     src->weakDefCanBeHidden);
 }
 
 Symbol *SymbolTable::addUndefined(StringRef name, InputFile *file,
                                   bool isWeakRef) {
   auto [s, wasInserted] = insert(name, file);
 

lld/MachO/Symbols.h

 public:
   enum Kind {
     DefinedKind,
     UndefinedKind,
     CommonKind,
     DylibKind,
     LazyArchiveKind,
     LazyObjectKind,
+    AliasKind,
   };
 
   virtual ~Symbol() {}
 
   Kind kind() const { return symbolKind; }
 
   StringRef getName() const {
     if (nameSize == (uint32_t)-1)
public:
   LazyObject(InputFile &file, StringRef name)
       : Symbol(LazyObjectKind, name, &file) {
     isUsedInRegularObj = false;
   }
 
   static bool classof(const Symbol *s) { return s->kind() == LazyObjectKind; }
 };
 
+// Represents N_INDR symbols. Note that if we are given valid, linkable inputs,
+// then all AliasSymbols in the input will be converted into one of the other
+// non-Lazy symbol types after `createAliases()` runs.
+class AliasSymbol final : public Symbol {
+public:
+  AliasSymbol(InputFile *file, StringRef name, StringRef aliasedName,
+              bool isPrivateExtern)
+      : Symbol(AliasKind, name, file), privateExtern(isPrivateExtern),
+        aliasedName(aliasedName) {}
+
+  StringRef getAliasedName() const { return aliasedName; }
+
+  static bool classof(const Symbol *s) { return s->kind() == AliasKind; }
+
+  const bool privateExtern;
+
+private:
+  StringRef aliasedName;
+};
+
 union SymbolUnion {
   alignas(Defined) char a[sizeof(Defined)];
   alignas(Undefined) char b[sizeof(Undefined)];
   alignas(CommonSymbol) char c[sizeof(CommonSymbol)];
   alignas(DylibSymbol) char d[sizeof(DylibSymbol)];
   alignas(LazyArchive) char e[sizeof(LazyArchive)];
   alignas(LazyObject) char f[sizeof(LazyObject)];
+  alignas(AliasSymbol) char g[sizeof(AliasSymbol)];
 };
 
 template <typename T, typename... ArgT>
 T *replaceSymbol(Symbol *s, ArgT &&...arg) {
   static_assert(sizeof(T) <= sizeof(SymbolUnion), "SymbolUnion too small");
   static_assert(alignof(T) <= alignof(SymbolUnion),
                 "SymbolUnion not aligned enough");
   assert(static_cast<Symbol *>(static_cast<T *>(nullptr)) == nullptr &&

lld/test/MachO/cli-aliases.s

 # REQUIRES: x86
 # RUN: rm -rf %t; split-file %s %t
 
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/foo.o %t/foo.s
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-macos -o %t/main.o %t/main.s
 
 # RUN: %lld -alias _foo _bar -u _bar -exported_symbol _bar %t/main.o %t/foo.o -o %t/bar.o
 # RUN: llvm-nm %t/bar.o | FileCheck %s --check-prefix=BAR
 
 # BAR: [[#%x,FOO_ADDR:]] T _bar
 # BAR: [[#FOO_ADDR]]     t _foo
 
 # RUN: not %lld -alias _missing _bar -alias _missing2 _baz %t/main.o -o %t/missing.o %s 2>&1 | FileCheck %s --check-prefix=MISSING
 
 # MISSING-DAG: undefined base symbol '_missing' for alias '_bar'
 # MISSING-DAG: undefined base symbol '_missing2' for alias '_baz'
 
 # RUN: %lld -alias _foo _main %t/foo.o -o %t/main_rename.o
 # RUN: llvm-nm %t/main_rename.o | FileCheck %s --check-prefix=MAIN
 
 # MAIN: [[#%x,FOO_ADDR:]] T _foo
 # MAIN: [[#FOO_ADDR]]     T _main
 
 # RUN: %lld -alias _foo _bar -alias _main _fake_main %t/main.o %t/foo.o -o %t/multiple.o
 # RUN: llvm-nm %t/multiple.o | FileCheck %s --check-prefix=MULTIPLE
 
 # MULTIPLE: [[#%x,FOO_ADDR:]]  T _bar
 # MULTIPLE: [[#%x,MAIN_ADDR:]] T _fake_main
 # MULTIPLE: [[#FOO_ADDR]]      T _foo
 # MULTIPLE: [[#MAIN_ADDR]]     T _main
 
 #--- foo.s
 .globl _foo
 _foo:
   ret
 
 #--- main.s
 .globl _main
 _main:
   ret

lld/test/MachO/symbol-aliases.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/aliases.s -o %t/aliases.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/definitions.s -o %t/definitions.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/alias-to-strong.s -o %t/alias-to-strong.o
+
+# RUN: %lld -lSystem %t/aliases.o %t/definitions.o -o %t/out
+# RUN: llvm-objdump --macho --syms %t/out | FileCheck %s
+
+## local aliases should be dropped entirely. --implicit-check-not doesn't seem
+## to work well with -DAG matches, so we check for _local_alias' absence in a
+## separate step.
+# RUN: llvm-objdump --macho --syms %t/out | FileCheck /dev/null --implicit-check-not _local_alias
+
+# CHECK-DAG: [[#%.16x,STRONG:]] g     F __TEXT,__text _strong
+# CHECK-DAG: [[#%.16x,WEAK:]]    w    F __TEXT,__text _weak
+# CHECK-DAG: [[#%.16x,DEAD:]]   g     F __TEXT,__text _dead
+# CHECK-DAG: [[#STRONG]]        l     F __TEXT,__text _pext_alias
+# CHECK-DAG: [[#STRONG]]        g     F __TEXT,__text _extern_alias_to_strong
+# CHECK-DAG: [[#WEAK]]           w    F __TEXT,__text _extern_alias_to_weak
+# CHECK-DAG: [[#DEAD]]          g     F __TEXT,__text _no_dead_strip_alias
+# CHECK-DAG: [[#STRONG]]        g     F __TEXT,__text _weak_extern_alias_to_strong
+
+# RUN: %lld -lSystem -dead_strip %t/aliases.o %t/definitions.o -o %t/dead-stripped
+# RUN: llvm-objdump --macho --syms %t/dead-stripped | FileCheck %s --check-prefix=STRIPPED
+
+# STRIPPED:      SYMBOL TABLE:
+# STRIPPED-NEXT: g     F __TEXT,__text _main
+# STRIPPED-NEXT: g     F __TEXT,__text __mh_execute_header
+# STRIPPED-NEXT:         *UND* dyld_stub_binder
+# STRIPPED-EMPTY:
+
+# RUN: not %lld -lSystem %t/aliases.o %t/definitions.o %t/alias-to-strong.o \
+# RUN:   -o /dev/null 2>&1 | FileCheck %s --check-prefix=DUP
+
+## Verify that we preserve the file names of the aliases, rather than using the
+## filename of the aliased symbols.
+# DUP:      error: duplicate symbol: _weak_extern_alias_to_strong
+# DUP-NEXT: >>> defined in {{.*}}aliases.o
+# DUP-NEXT: >>> defined in {{.*}}alias-to-strong.o
+
+#--- aliases.s
+.globl _extern_alias_to_strong, _extern_alias_to_weak, _extern_alias_to_weak
+
+## Private extern aliases result in local symbols in the output (i.e. it is as
+## if the aliased symbol is also private extern.)
+.private_extern _pext_alias
+
+## This test case demonstrates that it doesn't matter whether the alias itself
+## is strong or weak. Rather, what matters is whether the aliased symbol is
+## strong or weak.
+.globl _weak_extern_alias_to_strong
+.weak_definition _weak_extern_alias_to_strong
+
+## no_dead_strip doesn't retain the aliased symbol if it is dead
+.globl _no_dead_strip_alias
+.no_dead_strip _no_dead_strip_alias
+
+_extern_alias_to_strong = _strong
+_extern_alias_to_weak = _weak
+_weak_extern_alias_to_strong = _strong
+
+_pext_alias = _strong
+_local_alias = _strong
+_no_dead_strip_alias = _dead
+
+.subsections_via_symbols
+
+#--- definitions.s
+.globl _strong, _weak, _dead, _extern_alias_to_weak
+.weak_definition _weak
+
+_extern_alias_to_weak = _weak
+
+_strong:
+  .space 1
+_weak:
+  .space 1
+_dead:
+  .space 1
+
+.globl _main
+_main:
+
+.subsections_via_symbols
+
+#--- alias-to-strong.s
+.globl _weak_extern_alias_to_strong
+.weak_definition _weak_extern_alias_to_strong
+_weak_extern_alias_to_strong = _strong