[lld-macho] Initial support for common symbols

[int3]

Summary

On Unix, it is traditionally allowed to write variable definitions without
initialization expressions (such as "int foo;") to header files. These are
called tentative definitions.

The compiler creates common symbols when it sees tentative definitions. When
linking the final binary, if there are remaining common symbols after name
resolution is complete, the linker converts them to regular defined symbols in
a __common section.

This diff implements most of that functionality, though we do not yet handle
the case where there are both common and non-common definitions of the same
symbol.

[MaskRay]

Some interesting tests

• common.o regular.o - Does regular.o win?
• common.o archive.a (archive.a has a regular definition) - Is the regular definition in archive.a fetched? GNU ld's ELF port fetches archive.a in this case (Sun/HP-UX behavior https://sourceware.org/pipermail/binutils/1999-December/001283.html). lld/ELF doesn't
• common.o archive.a (archive.a has a common) - Is the regular definition in archive.a fetched?
• common.o shared.so - Does common.o win? In ELF, common-shared.s

• common0.o common1.o - the larger size is picked. the larger alignment is picked.

[int3]

@MaskRay -- I split the common vs non-common symbol handling into D86910. Sorry if that made it confusing... I think it covers all those cases you mentioned, aside from

common.o archive.a (archive.a has a common) - Is the regular definition in archive.a fetched?

I will add that.

common0.o common1.o - the larger size is picked. the larger alignment is picked.

Unlike lld-ELF, ld64 actually just picks the larger size, so I've emulated that here.

[MaskRay]

lld/MachO/SymbolTable.cpp

85

This is strange. Is it >?

[int3]

lld/MachO/SymbolTable.cpp

85

This is intentional. The same-size.s test verifies this behavior, and can be used to check that ld64 does the same thing.

[int3]

lld/MachO/SymbolTable.cpp

85

actually, I may have messed up the test...

[int3]

lld/MachO/SymbolTable.cpp

85

okay fixed. ld64 actually takes the smaller alignment if the sizes are equal. still different from lld-ELF's behavior though...

[int3]

fix

[MaskRay]

lld/MachO/SymbolTable.cpp

85

This rule is hard to believe...

A larger alignment imposes a larger requirement. Shouldn't the larger alignment be used?

In ELF, size and align are separately considered.

[int3]

lld/MachO/SymbolTable.cpp

85

I dunno... ld64 really does seem to behave like this. I haven't found the corresponding part of its code that handles common symbol resolution though

ld64 does take a -max_default_common_align option, and I double-checked to make sure that the max was high enough that it wouldn't interfere with our test

[int3]

revert to original behavior, fix test, handle zero alignment

lld/MachO/SymbolTable.cpp

85

My bad... my initial test was wrong in two places, but the >= was actually correct. I've fixed the test and reverted the behavior to the original. I'm fairly confident that it is correctly replicating ld64's behavior now, though I do agree it's a little weird

[int3]

update SymbolUnion

[gkm]

lld/MachO/Driver.cpp

443

Nit, bordering on Super Nit:
Say more about the nature of this replacement

• replaceCommonSymbolsWithDefinedSymbols ?
• defineCommonSymbols ?
• upgradeCommonSymbolsToDefined ?

[int3]

lld/MachO/Driver.cpp

443

I agree the name could be more informative, but this name is taken from a similar function in lld-elf, and I'd prefer to match them where possible

[omjavaid]

I have temporarily reverted this change as i broke LLDB build on Arm http://lab.llvm.org:8011/builders/lldb-arm-ubuntu/builds/4409

[int3]

Whoops, I hadn't realized that the test failure was related to this diff. Thanks for catching it.

lld/MachO/Driver.cpp

if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
         dylibFile->reexport = true;
         return true;
       }
     }
   }
   return false;
 }
 
+// Replaces common symbols with defined symbols residing in __common sections.
+// This function must be called after all symbol names are resolved (i.e. after
+// all InputFiles have been loaded.) As a result, later operations won't see
+// any CommonSymbols.
+static void replaceCommonSymbols() {
+  for (macho::Symbol *sym : symtab->getSymbols()) {
+    auto *common = dyn_cast<CommonSymbol>(sym);
+    if (common == nullptr)
+      continue;
+
+    auto *isec = make<InputSection>();
+    isec->file = common->file;
+    isec->name = section_names::common;
+    isec->segname = segment_names::data;
+    isec->align = common->align;
+    // Casting to size_t will truncate large values on 32-bit architectures,
+    // but it's not really worth supporting the linking of 64-bit programs on
+    // 32-bit archs.
+    isec->data = {nullptr, static_cast<size_t>(common->size)};
+    isec->flags = S_ZEROFILL;
+    inputSections.push_back(isec);
+
+    replaceSymbol<Defined>(sym, sym->getName(), isec, /*value=*/0,
+                           /*isWeakDef=*/false,
+                           /*isExternal=*/true);
+  }
+}
+
 static inline char toLowerDash(char x) {
   if (x >= 'A' && x <= 'Z')
     return x - 'A' + 'a';
   else if (x == ' ')
     return '-';
   return x;
 }
 
bool macho::link(llvm::ArrayRef<const char *> argsArr, bool canExitEarly,
   // re-exported.
   for (opt::Arg *arg : args.filtered(OPT_sub_library)) {
     config->hasReexports = true;
     StringRef searchName = arg->getValue();
     if (!markSubLibrary(searchName))
       error("-sub_library " + searchName + " does not match a supplied dylib");
   }
 
+  replaceCommonSymbols();
+
   StringRef orderFile = args.getLastArgValue(OPT_order_file);
   if (!orderFile.empty())
     parseOrderFile(orderFile);
 
   if (config->outputType == MH_EXECUTE && !isa<Defined>(config->entry)) {
     error("undefined symbol: " + config->entry->getName());
     return false;
   }

lld/MachO/InputFiles.cpp

auto createDefined = [&](const structs::nlist_64 &sym, InputSection *isec,
     // Local defined symbol
     return make<Defined>(name, isec, value, sym.n_desc & N_WEAK_DEF,
                          /*isExternal=*/false);
   };
 
   for (size_t i = 0, n = nList.size(); i < n; ++i) {
     const structs::nlist_64 &sym = nList[i];
 
-    // Undefined symbol
-    if (!sym.n_sect) {
+    if ((sym.n_type & N_TYPE) == N_UNDF) {
       StringRef name = strtab + sym.n_strx;
-      symbols[i] = symtab->addUndefined(name);
+      symbols[i] = sym.n_value == 0
+                       ? symtab->addUndefined(name)
+                       : symtab->addCommon(name, this, sym.n_value,
+                                           1 << GET_COMM_ALIGN(sym.n_desc));
       continue;
     }
 
     const section_64 &sec = sectionHeaders[sym.n_sect - 1];
     SubsectionMap &subsecMap = subsections[sym.n_sect - 1];
     uint64_t offset = sym.n_value - sec.addr;
 
     // If the input file does not use subsections-via-symbols, all symbols can

lld/MachO/SymbolTable.h

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Object/Archive.h"
 
 namespace lld {
 namespace macho {
 
 class ArchiveFile;
 class DylibFile;
+class InputFile;
 class InputSection;
 class MachHeaderSection;
 class Symbol;
 
 /*
  * Note that the SymbolTable handles name collisions by calling
  * replaceSymbol(), which does an in-place update of the Symbol via `placement
  * new`. Therefore, there is no need to update any relocations that hold
  * pointers the "old" Symbol -- they will automatically point to the new one.
  */
 class SymbolTable {
 public:
   Symbol *addDefined(StringRef name, InputSection *isec, uint32_t value,
                      bool isWeakDef);
 
   Symbol *addUndefined(StringRef name);
 
+  Symbol *addCommon(StringRef name, InputFile *, uint64_t size, uint32_t align);
+
   Symbol *addDylib(StringRef name, DylibFile *file, bool isWeakDef, bool isTlv);
 
   Symbol *addLazy(StringRef name, ArchiveFile *file,
                   const llvm::object::Archive::Symbol &sym);
 
   Symbol *addDSOHandle(const MachHeaderSection *);
 
   ArrayRef<Symbol *> getSymbols() const { return symVector; }

lld/MachO/SymbolTable.cpp

Symbol *SymbolTable::addUndefined(StringRef name) {
 
   if (wasInserted)
     replaceSymbol<Undefined>(s, name);
   else if (LazySymbol *lazy = dyn_cast<LazySymbol>(s))
     lazy->fetchArchiveMember();
   return s;
 }
 
+Symbol *SymbolTable::addCommon(StringRef name, InputFile *file, uint64_t size,
+                               uint32_t align) {
+  Symbol *s;
+  bool wasInserted;
+  std::tie(s, wasInserted) = insert(name);
+
+  if (!wasInserted) {
+    if (auto *common = dyn_cast<CommonSymbol>(s)) {
+      if (size < common->size)
+        return s;
+    } else if (!isa<Undefined>(s)) {
+      error("TODO: implement common symbol resolution with other symbol kinds");
+      return s;
+    }
+  }
+
+  replaceSymbol<CommonSymbol>(s, name, file, size, align);
+  return s;
+}
+
 Symbol *SymbolTable::addDylib(StringRef name, DylibFile *file, bool isWeakDef,
                               bool isTlv) {
   Symbol *s;
   bool wasInserted;
   std::tie(s, wasInserted) = insert(name);
 
   if (!wasInserted && isWeakDef)
     if (auto *defined = dyn_cast<Defined>(s))

lld/MachO/Symbols.h

 //===- Symbols.h ------------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_SYMBOLS_H
 #define LLD_MACHO_SYMBOLS_H
 
 #include "InputSection.h"
 #include "Target.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Strings.h"
 #include "llvm/Object/Archive.h"
+#include "llvm/Support/MathExtras.h"
 
 namespace lld {
 namespace macho {
 
 class InputSection;
 class MachHeaderSection;
 class DylibFile;
 class ArchiveFile;
 
 struct StringRefZ {
   StringRefZ(const char *s) : data(s), size(-1) {}
   StringRefZ(StringRef s) : data(s.data()), size(s.size()) {}
 
   const char *data;
   const uint32_t size;
 };
 
 class Symbol {
 public:
   enum Kind {
     DefinedKind,
     UndefinedKind,
+    CommonKind,
     DylibKind,
     LazyKind,
     DSOHandleKind,
   };
 
   virtual ~Symbol() {}
 
   Kind kind() const { return static_cast<Kind>(symbolKind); }

 
 class Undefined : public Symbol {
 public:
   Undefined(StringRefZ name) : Symbol(UndefinedKind, name) {}
 
   static bool classof(const Symbol *s) { return s->kind() == UndefinedKind; }
 };
 
+// On Unix, it is traditionally allowed to write variable definitions without
+// initialization expressions (such as "int foo;") to header files. These are
+// called tentative definitions.
+//
+// Using tentative definitions is usually considered a bad practice; you should
+// write only declarations (such as "extern int foo;") to header files.
+// Nevertheless, the linker and the compiler have to do something to support
+// bad code by allowing duplicate definitions for this particular case.
+//
+// The compiler creates common symbols when it sees tentative definitions.
+// (You can suppress this behavior and let the compiler create a regular
+// defined symbol by passing -fno-common.) When linking the final binary, if
+// there are remaining common symbols after name resolution is complete, the
+// linker converts them to regular defined symbols in a __common section.
+class CommonSymbol : public Symbol {
+public:
+  CommonSymbol(StringRefZ name, InputFile *file, uint64_t size, uint32_t align)
+      : Symbol(CommonKind, name), file(file), size(size),
+        align(align != 1 ? align : llvm::PowerOf2Ceil(size)) {
+    // TODO: cap maximum alignment
+  }
+
+  static bool classof(const Symbol *s) { return s->kind() == CommonKind; }
+
+  InputFile *const file;
+  const uint64_t size;
+  const uint32_t align;
+};
+
 class DylibSymbol : public Symbol {
 public:
   DylibSymbol(DylibFile *file, StringRefZ name, bool isWeakDef, bool isTlv)
       : Symbol(DylibKind, name), file(file), weakDef(isWeakDef), tlv(isTlv) {}
 
   bool isWeakDef() const override { return weakDef; }
   bool isTlv() const override { return tlv; }
   bool hasStubsHelper() const { return stubsHelperIndex != UINT32_MAX; }
public:
   static constexpr StringRef name = "___dso_handle";
 
   static bool classof(const Symbol *s) { return s->kind() == DSOHandleKind; }
 };
 
 union SymbolUnion {
   alignas(Defined) char a[sizeof(Defined)];
   alignas(Undefined) char b[sizeof(Undefined)];
-  alignas(DylibSymbol) char c[sizeof(DylibSymbol)];
-  alignas(LazySymbol) char d[sizeof(LazySymbol)];
+  alignas(CommonSymbol) char c[sizeof(CommonSymbol)];
+  alignas(DylibSymbol) char d[sizeof(DylibSymbol)];
+  alignas(LazySymbol) char e[sizeof(LazySymbol)];
+  alignas(DSOHandle) char f[sizeof(DSOHandle)];
 };
 
 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/MachO/SyntheticSections.h

 #include "llvm/Support/raw_ostream.h"
 
 namespace lld {
 namespace macho {
 
 namespace section_names {
 
 constexpr const char pageZero[] = "__pagezero";
+constexpr const char common[] = "__common";
 constexpr const char header[] = "__mach_header";
 constexpr const char binding[] = "__binding";
 constexpr const char weakBinding[] = "__weak_binding";
 constexpr const char lazyBinding[] = "__lazy_binding";
 constexpr const char export_[] = "__export";
 constexpr const char symbolTable[] = "__symbol_table";
 constexpr const char indirectSymbolTable[] = "__ind_sym_tab";
 constexpr const char stringTable[] = "__string_table";

lld/test/MachO/common-symbol-coalescing.s

+# REQUIRES: x86
+# RUN: split-file %s %t
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/same-size.s -o %t/same-size.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/smaller-size.s -o %t/smaller-size.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/zero-align.s -o %t/zero-align.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/zero-align-round-up.s -o %t/zero-align-round-up.o
+
+## Check that we pick the definition with the larger size, regardless of
+## its alignment.
+# RUN: lld -flavor darwinnew %t/test.o %t/smaller-size.o -order_file %t/order -o %t/test
+# RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s --check-prefix=SMALLER-ALIGNMENT
+# RUN: lld -flavor darwinnew %t/smaller-size.o %t/test.o -order_file %t/order -o %t/test
+# RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s --check-prefix=SMALLER-ALIGNMENT
+
+## When the sizes are equal, we pick the symbol whose file occurs later in the
+## command-line argument list.
+# RUN: lld -flavor darwinnew %t/test.o %t/same-size.o -order_file %t/order -o %t/test
+# RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s --check-prefix=LARGER-ALIGNMENT
+# RUN: lld -flavor darwinnew %t/same-size.o %t/test.o -order_file %t/order -o %t/test
+# RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s --check-prefix=SMALLER-ALIGNMENT
+
+# RUN: lld -flavor darwinnew %t/test.o %t/zero-align.o -order_file %t/order -o %t/test
+# RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s --check-prefix=LARGER-ALIGNMENT
+# RUN: lld -flavor darwinnew %t/zero-align.o %t/test.o -order_file %t/order -o %t/test
+# RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s --check-prefix=LARGER-ALIGNMENT
+
+# RUN: lld -flavor darwinnew %t/test.o %t/zero-align-round-up.o -order_file %t/order -o %t/test
+# RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s --check-prefix=LARGER-ALIGNMENT
+# RUN: lld -flavor darwinnew %t/zero-align-round-up.o %t/test.o -order_file %t/order -o %t/test
+# RUN: llvm-objdump --section-headers --syms %t/test | FileCheck %s --check-prefix=LARGER-ALIGNMENT
+
+# SMALLER-ALIGNMENT-LABEL: Sections:
+# SMALLER-ALIGNMENT:       __common      {{[0-9a-f]+}} [[#%x, COMMON_START:]]  BSS
+
+# SMALLER-ALIGNMENT-LABEL: SYMBOL TABLE:
+# SMALLER-ALIGNMENT-DAG:   [[#COMMON_START]]      g     O __DATA,__common _check_size
+# SMALLER-ALIGNMENT-DAG:   [[#COMMON_START + 2]]  g     O __DATA,__common _end_marker
+# SMALLER-ALIGNMENT-DAG:   [[#COMMON_START + 8]]  g     O __DATA,__common _check_alignment
+
+# LARGER-ALIGNMENT-LABEL: Sections:
+# LARGER-ALIGNMENT:       __common      {{[0-9a-f]+}} [[#%x, COMMON_START:]]  BSS
+
+# LARGER-ALIGNMENT-LABEL: SYMBOL TABLE:
+# LARGER-ALIGNMENT-DAG:   [[#COMMON_START]]      g     O __DATA,__common _check_size
+# LARGER-ALIGNMENT-DAG:   [[#COMMON_START + 2]]  g     O __DATA,__common _end_marker
+# LARGER-ALIGNMENT-DAG:   [[#COMMON_START + 16]] g     O __DATA,__common _check_alignment
+
+#--- order
+## Order is important as we determine the size of a given symbol via the
+## address of the next symbol.
+_check_size
+_end_marker
+_check_alignment
+
+#--- smaller-size.s
+.comm _check_size, 1, 1
+.comm _check_alignment, 1, 4
+
+#--- same-size.s
+.comm _check_size, 2, 1
+.comm _check_alignment, 2, 4
+
+#--- zero-align.s
+.comm _check_size, 2, 1
+## If alignment is set to zero, use the size to determine the alignment.
+.comm _check_alignment, 16, 0
+
+#--- zero-align-round-up.s
+.comm _check_size, 2, 1
+## If alignment is set to zero, use the size to determine the alignment. If the
+## size is not a power of two, round it up. (In this case, 14 rounds to 16.)
+.comm _check_alignment, 14, 0
+
+#--- test.s
+.comm _check_size, 2, 1
+.comm _end_marker, 1
+.comm _check_alignment, 2, 3
+
+.globl _main
+_main:
+  ret