[lld-macho] Don't merge cstrings across different sections

[int3]

Summary

I realized that ld64 merges word literals across sections, but
does not do the same for cstring literals. This diff brings us up to
parity + adds a test for the behavior around word literals as well.

[int3]

cleanup

[thakis]

Does supporting it cause problems?

[int3]

I don't know. I'm trying to debug a "unrecognized selector" crash in one of my programs right now, and so I've been looking at discrepancies between the ObjC-related data in LLD vs ld64's outputs. I saw that the __objc_methname and other similar strings in ld64's output remained in their original sections, whereas we were merging them all into __cstring. I don't think this diff fixes the original crash, but I figured having fewer discrepancies between the two binaries would be a good thing regardless.

However, if you would prefer we not land this until there's a demonstrated need, I'm with that too.

[int3]

Turns out D112500: [lld-macho] Put GOT into `__DATA` segment where appropriate fixed the "unrecognized selector" crash, so I guess I don't need this any more, at least for now

lld/MachO/Driver.cpp

for (const SubsectionMap &map : file->subsections) {
             continue;
           }
           isec->outSecOff = inputOrder++;
           if (!osec)
             osec = ConcatOutputSection::getOrCreateForInput(isec);
           isec->parent = osec;
           inputSections.push_back(isec);
         } else if (auto *isec = dyn_cast<CStringInputSection>(entry.isec)) {
-          if (in.cStringSection->inputOrder == UnspecifiedInputOrder)
-            in.cStringSection->inputOrder = inputOrder++;
-          in.cStringSection->addInput(isec);
+          // Unlike word literals, we cannot merge cstrings across sections, so
+          // we must create an output section per input cstring section type.
+          CStringSection *cStringSec =
+              CStringSection::getOrCreateForInput(isec);
+          if (cStringSec->inputOrder == UnspecifiedInputOrder)
+            cStringSec->inputOrder = inputOrder++;
+          cStringSec->addInput(isec);
         } else if (auto *isec = dyn_cast<WordLiteralInputSection>(entry.isec)) {
           if (in.wordLiteralSection->inputOrder == UnspecifiedInputOrder)
             in.wordLiteralSection->inputOrder = inputOrder++;
           in.wordLiteralSection->addInput(isec);
         } else {
           llvm_unreachable("unexpected input section kind");
         }
       }
     }
   }
   assert(inputOrder <= UnspecifiedInputOrder);
 }
 
 static void foldIdenticalLiterals() {
-  // We always create a cStringSection, regardless of whether dedupLiterals is
+  // We always create CStringSections, regardless of whether dedupLiterals is
   // true. If it isn't, we simply create a non-deduplicating CStringSection.
-  // Either way, we must unconditionally finalize it here.
-  in.cStringSection->finalizeContents();
+  // Either way, we must unconditionally finalize them here.
+  for (const auto &p : CStringSection::instanceMap)
+    p.second->finalizeContents();
   if (in.wordLiteralSection)
     in.wordLiteralSection->finalizeContents();
 }
 
 static void referenceStubBinder() {
   bool needsStubHelper = config->outputType == MH_DYLIB ||
                          config->outputType == MH_EXECUTE ||
                          config->outputType == MH_BUNDLE;

lld/MachO/SyntheticSections.h

 class Defined;
 class DylibSymbol;
 class LoadCommand;
 class ObjFile;
 class UnwindInfoSection;
 
 class SyntheticSection : public OutputSection {
 public:
-  SyntheticSection(const char *segname, const char *name);
+  SyntheticSection(StringRef segname, StringRef name);
   virtual ~SyntheticSection() = default;
 
   static bool classof(const OutputSection *sec) {
     return sec->kind() == SyntheticKind;
   }
 
   StringRef segname;
   // This fake InputSection makes it easier for us to write code that applies

 
 private:
   llvm::SmallString<261> xarPath;
   uint64_t xarSize;
 };
 
 class CStringSection : public SyntheticSection {
 public:
-  CStringSection();
+  CStringSection(StringRef segname, StringRef name);
   void addInput(CStringInputSection *);
   uint64_t getSize() const override { return size; }
   virtual void finalizeContents();
   bool isNeeded() const override { return !inputs.empty(); }
   void writeTo(uint8_t *buf) const override;
 
+  static llvm::DenseMap<NamePair, CStringSection *> instanceMap;
+  // Returns either a CStringSection or a DeduplicatedCStringSection.
+  static CStringSection *getOrCreateForInput(const CStringInputSection *);
+
   std::vector<CStringInputSection *> inputs;
 
 private:
   uint64_t size;
 };
 
 class DeduplicatedCStringSection final : public CStringSection {
 public:
-  DeduplicatedCStringSection();
+  DeduplicatedCStringSection(StringRef segname, StringRef name);
   uint64_t getSize() const override { return builder.getSize(); }
   void finalizeContents() override;
   void writeTo(uint8_t *buf) const override { builder.write(buf); }
 
 private:
   llvm::StringTableBuilder builder;
 };
 
private:
   // values for DenseMap.
   std::unordered_map<UInt128, uint64_t, Hasher<UInt128>> literal16Map;
   std::unordered_map<uint64_t, uint64_t> literal8Map;
   std::unordered_map<uint32_t, uint64_t> literal4Map;
 };
 
 struct InStruct {
   MachHeaderSection *header = nullptr;
-  CStringSection *cStringSection = nullptr;
   WordLiteralSection *wordLiteralSection = nullptr;
   RebaseSection *rebase = nullptr;
   BindingSection *binding = nullptr;
   WeakBindingSection *weakBinding = nullptr;
   LazyBindingSection *lazyBinding = nullptr;
   ExportSection *exports = nullptr;
   GotSection *got = nullptr;
   TlvPointerSection *tlvPointers = nullptr;

lld/MachO/SyntheticSections.cpp

 using namespace llvm::support;
 using namespace llvm::support::endian;
 using namespace lld;
 using namespace lld::macho;
 
 InStruct macho::in;
 std::vector<SyntheticSection *> macho::syntheticSections;
 
-SyntheticSection::SyntheticSection(const char *segname, const char *name)
+SyntheticSection::SyntheticSection(StringRef segname, StringRef name)
     : OutputSection(SyntheticKind, name) {
   std::tie(this->segname, this->name) = maybeRenameSection({segname, name});
   isec = make<ConcatInputSection>(segname, name);
   isec->parent = this;
   syntheticSections.push_back(this);
 }
 
 // dyld3's MachOLoaded::getSlide() assumes that the __TEXT segment starts
void BitcodeBundleSection::writeTo(uint8_t *buf) const {
   if (ec)
     fatal("failed to map XAR file");
   memcpy(buf, xarMap.const_data(), xarSize);
 
   closeFile(handle);
   remove(xarPath);
 }
 
-CStringSection::CStringSection()
-    : SyntheticSection(segment_names::text, section_names::cString) {
+CStringSection::CStringSection(StringRef segname, StringRef name)
+    : SyntheticSection(segname, name) {
   flags = S_CSTRING_LITERALS;
 }
 
 void CStringSection::addInput(CStringInputSection *isec) {
   isec->parent = this;
   inputs.push_back(isec);
   if (isec->align > align)
     align = isec->align;
for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
       isec->pieces[i].outSecOff = offset;
       isec->isFinal = true;
       StringRef string = isec->getStringRef(i);
       offset += string.size();
     }
   }
   size = offset;
 }
+
+DenseMap<NamePair, CStringSection *> CStringSection::instanceMap;
+
+CStringSection *
+CStringSection::getOrCreateForInput(const CStringInputSection *isec) {
+  NamePair names = maybeRenameSection({isec->getSegName(), isec->getName()});
+  CStringSection *&osec = instanceMap[names];
+  if (!osec) {
+    if (config->dedupLiterals)
+      osec = make<DeduplicatedCStringSection>(names.first, names.second);
+    else
+      osec = make<CStringSection>(names.first, names.second);
+  }
+  return osec;
+}
+
 // Mergeable cstring literals are found under the __TEXT,__cstring section. In
 // contrast to ELF, which puts strings that need different alignments into
 // different sections, clang's Mach-O backend puts them all in one section.
 // Strings that need to be aligned have the .p2align directive emitted before
 // them, which simply translates into zero padding in the object file.
 //
 // I *think* ld64 extracts the desired per-string alignment from this data by
 // preserving each string's offset from the last section-aligned address. I'm
 // not entirely certain since it doesn't seem consistent about doing this, and
 // in fact doesn't seem to be correct in general: we can in fact can induce ld64
 // to produce a crashing binary just by linking in an additional object file
 // that only contains a duplicate cstring at a different alignment. See PR50563
 // for details.
 //
 // On x86_64, the cstrings we've seen so far that require special alignment are
 // all accessed by SIMD operations -- x86_64 requires SIMD accesses to be
 // 16-byte-aligned. arm64 also seems to require 16-byte-alignment in some cases
 // (PR50791), but I haven't tracked down the root cause. So for now, I'm just
 // aligning all strings to 16 bytes.  This is indeed wasteful, but
 // implementation-wise it's simpler than preserving per-string
 // alignment+offsets. It also avoids the aforementioned crash after
 // deduplication of differently-aligned strings.  Finally, the overhead is not
 // huge: using 16-byte alignment (vs no alignment) is only a 0.5% size overhead
 // when linking chromium_framework on x86_64.
-DeduplicatedCStringSection::DeduplicatedCStringSection()
-    : builder(StringTableBuilder::RAW, /*Alignment=*/16) {}
+DeduplicatedCStringSection::DeduplicatedCStringSection(StringRef segname,
+                                                       StringRef name)
+    : CStringSection(segname, name),
+      builder(StringTableBuilder::RAW, /*Alignment=*/16) {}
 
 void DeduplicatedCStringSection::finalizeContents() {
   // Add all string pieces to the string table builder to create section
   // contents.
   for (const CStringInputSection *isec : inputs)
     for (size_t i = 0, e = isec->pieces.size(); i != e; ++i)
       if (isec->pieces[i].live)
         builder.add(isec->getCachedHashStringRef(i));

lld/MachO/Writer.cpp

template <class LP> void Writer::run() {
   writeMapFile();
   writeOutputFile();
 }
 
 template <class LP> void macho::writeResult() { Writer().run<LP>(); }
 
 void macho::createSyntheticSections() {
   in.header = make<MachHeaderSection>();
-  if (config->dedupLiterals) {
-    in.cStringSection = make<DeduplicatedCStringSection>();
-  } else {
-    in.cStringSection = make<CStringSection>();
-  }
   in.wordLiteralSection =
       config->dedupLiterals ? make<WordLiteralSection>() : nullptr;
   in.rebase = make<RebaseSection>();
   in.binding = make<BindingSection>();
   in.weakBinding = make<WeakBindingSection>();
   in.lazyBinding = make<LazyBindingSection>();
   in.exports = make<ExportSection>();
   in.got = make<GotSection>();

lld/test/MachO/cstring-dedup.s

 # REQUIRES: x86
 # RUN: rm -rf %t; 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/more-foo.s -o %t/more-foo.o
-# RUN: %lld -dylib --deduplicate-literals %t/test.o %t/more-foo.o -o %t/test
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/name-collision.s -o %t/name-collision.o
+# RUN: %lld -dylib --deduplicate-literals \
+# RUN:   -rename_section __TEXT more_cstrings __TEXT renamed \
+# RUN:   %t/test.o %t/more-foo.o -o %t/test
 # RUN: llvm-objdump --macho --section="__TEXT,__cstring" %t/test | \
 # RUN:   FileCheck %s --check-prefix=STR --implicit-check-not foo --implicit-check-not bar
+# RUN: llvm-objdump --macho --section="__TEXT,renamed" %t/test | \
+# RUN:   FileCheck %s --check-prefix=MORE-STR --implicit-check-not foo --implicit-check-not bar
 # RUN: llvm-objdump --macho --section="__DATA,ptrs" --syms %t/test | FileCheck %s
 # RUN: llvm-readobj --section-headers %t/test | FileCheck %s --check-prefix=HEADER
 
+# RUN: not %lld -dylib --deduplicate-literals \
+# RUN:   -rename_section __TEXT more_cstrings __TEXT renamed \
+# RUN:   %t/test.o %t/more-foo.o %t/name-collision.o -o /dev/null 2>&1 | \
+# RUN:   FileCheck %s --check-prefix=CONFLICT
+# CONFLICT: section from {{.*}}name-collision.o conflicts with synthetic section __TEXT,renamed
+
 ## Make sure we only have 3 deduplicated strings in __cstring, and that they
 ## are 16-byte-aligned.
 # STR: Contents of (__TEXT,__cstring) section
 # STR: {{.*}}0 foo
 # STR: {{.*}}0 barbaz
 # STR: {{.*}}0 {{$}}
 
+## Make sure strings get deduplicated within each section, but not across
+## sections.
+# MORE-STR: Contents of (__TEXT,renamed) section
+# MORE-STR: foo
+# MORE-STR: barbaz
+# MORE-STR: {{$}}
+
 ## Make sure both symbol and section relocations point to the right thing.
 # CHECK:      Contents of (__DATA,ptrs) section
 # CHECK-NEXT: __TEXT:__cstring:foo
 # CHECK-NEXT: __TEXT:__cstring:foo
 # CHECK-NEXT: __TEXT:__cstring:foo
 # CHECK-NEXT: __TEXT:__cstring:foo
 # CHECK-NEXT: __TEXT:__cstring:foo
 # CHECK-NEXT: __TEXT:__cstring:foo
_local_foo2:
   .asciz "foo"
 L_.foo1:
   .asciz "foo"
 L_.foo2:
   .asciz "foo"
 
 _bar1:
   .ascii "bar"
+## NOTE: ld64 doesn't actually support having symbols point to the middle of a
+## cstring. It crashes with a "more atoms allocated than expected" error. We
+## can remove LLD's support for this "feature" if necessary.
 _baz1:
   .asciz "baz"
 _bar2:
   .ascii "bar"
 _baz2:
   .asciz "baz"
 
 _zero1:
   .asciz ""
 _zero2:
   .asciz ""
 
+.section __TEXT,more_cstrings,cstring_literals
+.p2align 2
+.asciz "foo"
+.asciz "foo"
+.asciz "barbaz"
+
 .section __DATA,ptrs,literal_pointers
 .quad L_.foo1
 .quad L_.foo2
 .quad _local_foo1
 .quad _local_foo2
 .quad _globl_foo1
 .quad _globl_foo2
 .quad _bar1
 .quad _baz1
 .quad _bar2
 .quad _baz2
 .quad _zero1
 .quad _zero2
 
 #--- more-foo.s
 .globl _globl_foo1, _globl_foo2
 .cstring
 .p2align 4
 _globl_foo1:
   .asciz "foo"
 _globl_foo2:
   .asciz "foo"
+
+#--- name-collision.s
+.section __TEXT,renamed
+.space 1

lld/test/MachO/literal-dedup.s

 # REQUIRES: x86
 # RUN: rm -rf %t; 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/qux.s -o %t/qux.o
 # RUN: %lld -dylib --deduplicate-literals %t/test.o %t/qux.o -o %t/test
+# RUN: llvm-objdump --macho --section-headers %t/test | FileCheck %s --check-prefix=SECTIONS
 # RUN: llvm-objdump --macho --section="__TEXT,__literals" --section="__DATA,ptrs" --syms %t/test | FileCheck %s
 # RUN: llvm-readobj --section-headers %t/test | FileCheck %s --check-prefix=HEADER
 
+## Check that all literal input sections are folded into `__literals`,
+## regardless of their original names
+# SECTIONS:       0 __text
+# SECTIONS-NEXT:  1 __literals
+# SECTIONS-NEXT:  2 ptrs
+# SECTIONS-EMPTY:
+
 # CHECK:      Contents of (__TEXT,__literals) section
 # CHECK-NEXT: [[#%.16x,DEADBEEF16:]] ef be ad de ef be ad de ef be ad de ef be ad de
 # CHECK-NEXT: [[#%.16x,FEEDFACE16:]] ce fa ed fe ce fa ed fe ce fa ed fe ce fa ed fe
 # CHECK-NEXT: [[#%.16x,DEADBEEF8:]]  ef be ad de ef be ad de ce fa ed fe ce fa ed fe
 # CHECK-NEXT: [[#%.16x,DEADBEEF4:]]  ef be ad de ce fa ed fe
 # CHECK-NEXT: Contents of (__DATA,ptrs) section
 # CHECK-NEXT: 0000000000001000  0x[[#%x,DEADBEEF16]]
 # CHECK-NEXT: 0000000000001008  0x[[#%x,DEADBEEF16]]
 # CHECK-NEXT: 0000000000001010  0x[[#%x,FEEDFACE16]]
 # CHECK-NEXT: 0000000000001018  0x[[#%x,DEADBEEF16]]
 # CHECK-NEXT: 0000000000001020  0x[[#%x,DEADBEEF8]]
 # CHECK-NEXT: 0000000000001028  0x[[#%x,DEADBEEF8]]
 # CHECK-NEXT: 0000000000001030  0x[[#%x,DEADBEEF8 + 8]]
 # CHECK-NEXT: 0000000000001038  0x[[#%x,DEADBEEF8]]
 # CHECK-NEXT: 0000000000001040  0x[[#%x,DEADBEEF4]]
 # CHECK-NEXT: 0000000000001048  0x[[#%x,DEADBEEF4]]
 # CHECK-NEXT: 0000000000001050  0x[[#%x,DEADBEEF4 + 4]]
 # CHECK-NEXT: 0000000000001058  0x[[#%x,DEADBEEF4]]
+# CHECK-EMPTY:
 
 ## Make sure the symbol addresses are correct too.
 # CHECK:     SYMBOL TABLE:
 # CHECK-DAG: [[#DEADBEEF16]] g     O __TEXT,__literals _qux16
 # CHECK-DAG: [[#DEADBEEF8]]  g     O __TEXT,__literals _qux8
 # CHECK-DAG: [[#DEADBEEF4]]  g     O __TEXT,__literals _qux4
 
 ## Make sure we set the right alignment and flags.

 .p2align 2
 L._foo4:
   .long 0xdeadbeef
 L._bar4:
   .long 0xdeadbeef
 L._baz4:
   .long 0xfeedface
 
+.section __TEXT,more_lit4,4byte_literals
+  .long 0xdeadbeef
+
 .literal8
 L._foo8:
   .quad 0xdeadbeefdeadbeef
 L._bar8:
   .quad 0xdeadbeefdeadbeef
 L._baz8:
   .quad 0xfeedfacefeedface