[lld-macho] Preserve alignment for non-deduplicated cstrings

[lgrey]

Summary

Fixes PR50637

Downstream bug: https://crbug.com/1218958

Currently, we split __cstring along symbol boundaries with .subsections_via_symbols
when not deduplicating, and along null bytes when deduplicating. This change splits
along null bytes unconditionally, and preserves original alignment in the non-
deduplicated case.

Removing subsections-section-relocs.s because with this change, __cstring
is never reordered based on the order file. From offline conversation, thakis@
believes that the new test sufficiently exercises splitting.

[lgrey]

Rebase

[thakis]

Nice!

Add "Fixes PR50637" to the commit message, since it fixes llvm.org/PR50637

I'd word the commit message as "__cstring is special in that it is split at null bytes instead of at symbol boundaries with .subsections_via_symbols" or something like that.

Please mention in the patch description why you're removing subsections-section-relocs.s.

lld/MachO/SyntheticSections.cpp

1191

I think that'd be nice. You just need

% git diff
diff --git a/lld/MachO/InputSection.h b/lld/MachO/InputSection.h
index 3dd31d27be91..413b7aed70e7 100644
--- a/lld/MachO/InputSection.h
+++ b/lld/MachO/InputSection.h
@@ -183,11 +183,15 @@ public:
   // Returns i'th piece as a CachedHashStringRef. This function is very hot when
   // string merging is enabled, so we want to inline.
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  llvm::CachedHashStringRef getCachedHashStringRef(size_t i) const {
+  StringRef getStringRef(size_t i) const {
     size_t begin = pieces[i].inSecOff;
     size_t end =
         (pieces.size() - 1 == i) ? data.size() : pieces[i + 1].inSecOff;
-    return {toStringRef(data.slice(begin, end - begin)), pieces[i].hash};
+    return toStringRef(data.slice(begin, end - begin));
+  }
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  llvm::CachedHashStringRef getCachedHashStringRef(size_t i) const {
+    return {getStringRef(i), pieces[i].hash};
   }

   static bool classof(const InputSection *isec) {

and then you could call getStringRef() here, right?

lld/MachO/SyntheticSections.h

530

Maybe this should just be the default impl in CStringSection and DedupStringSection overrides it?

[thakis]

lld/MachO/SyntheticSections.cpp

1191

(and give splitIntoPieces() a toggle to control if it computes a hash or not.)

[lgrey]

• Collapse class hierarchy so CStringSection handles the non dedup case
• Make string hashing optional, and only do when deduping
• Update commit message

[lgrey]

lld/MachO/SyntheticSections.cpp

1191

Baked it into the implementation

[thakis]

Oh, I didn't realize this breaks -order_file for strings. But I think it's fine to leave this for a follow-up. --deduplicate-strings already has that bug after all, and not creating crashing binaries is definitely better than not being able to reorder strings :)

lg. Let's wait a few hours to see if anyone else chimes in. If not, I'll land this for you.

(I kind of wish we could put make InputSection small and fast enough that we could just do one regular InputSection per string....)

[int3]

Oh, I didn't realize this breaks -order_file for strings

I think it's fine actually -- in theory, cstrings can be reordered based on their literal values (instead of via symbol names) -- or at least that's what ld64's manpage suggests. In practice it doesn't actually seem to work. So we can probably come up with an alternative ordering mechanism for cstrings at some point

(I kind of wish we could put make InputSection small and fast enough that we could just do one regular InputSection per string....)

FWIW, I belatedly realized that my benchmarking diff D104159 (and the current StringPiece implementation) has a flaw: they create one InputSection/StringPiece respectively for every null byte, and since the Mach-O format employs zero padding extensively for alignment, we're actually allocating a bunch of useless stuff for zero-length strings. I guess this isn't an issue with ELF since it creates separate sections for strings that need to be aligned.

lld/test/MachO/dead-strip-align.s

2

needs a # REQUIRES: x86 line above

14

should we test for a non-zero offset as well?

21

this section header is redundant

26

ditto

[thakis]

I think it's fine actually -- in theory, cstrings can be reordered based on their literal values (instead of via symbol names) -- or at least that's what ld64's manpage suggests. In practice it doesn't actually seem to work.

Works for me:

thakis@MBP llvm-project % cat strings.cc
const char k1[] = "hi";
const char k2[] = "hallo";

extern "C" int puts(const char*);

int main() {
  puts(k1);
  puts(k2);
}
thakis@MBP llvm-project % clang strings.cc
thakis@MBP llvm-project % otool -s __TEXT __const a.out
a.out:
Contents of (__TEXT,__const) section
0000000100003fa2	68 69 00 68 61 6c 6c 6f 00
thakis@MBP llvm-project % clang strings.cc -Wl,-order_file,order.txt
thakis@MBP llvm-project % otool -s __TEXT __const a.out
a.out:
Contents of (__TEXT,__const) section
0000000100003fa2	68 61 6c 6c 6f 00 68 69 00
thakis@MBP llvm-project % cat order.txt
__ZL2k2
__ZL2k1

[int3]

Ah. I meant that an order file like

"hi"
"hallo"

Should work according to ld64's manpage (and its code), but doesn't seem to work in practice. Didn't think about the regular symbol case, I guess it might be worthwhile to find some way to make that still work. (Alternatively, maybe just supporting literal-value-based ordering will be good enough?)

[lgrey]

Test update

lld/test/MachO/dead-strip-align.s

14

How's this?

[int3]

do remember to clang-format before you land :)

lld/test/MachO/dead-strip-align.s

14

lg, thanks!

[lgrey]

Format

lld/MachO/InputFiles.cpp

if (sec.align >= 32) {
       error("alignment " + std::to_string(sec.align) + " of section " + name +
             " is too large");
       subsections.push_back({});
       continue;
     }
     uint32_t align = 1 << sec.align;
     uint32_t flags = sec.flags;
 
-    if (config->dedupLiterals &&
-        (sectionType(sec.flags) == S_CSTRING_LITERALS ||
-         isWordLiteralSection(sec.flags))) {
-      if (sec.nreloc)
+    if (sectionType(sec.flags) == S_CSTRING_LITERALS ||
+        (config->dedupLiterals && isWordLiteralSection(sec.flags))) {
+      if (sec.nreloc && config->dedupLiterals)
         fatal(toString(this) + " contains relocations in " + sec.segname + "," +
               sec.sectname +
               ", so LLD cannot deduplicate literals. Try re-running without "
               "--deduplicate-literals.");
 
       InputSection *isec;
       if (sectionType(sec.flags) == S_CSTRING_LITERALS) {
         isec =

lld/MachO/InputSection.h

 }
 
 // We allocate a lot of these and binary search on them, so they should be as
 // compact as possible. Hence the use of 31 rather than 64 bits for the hash.
 struct StringPiece {
   // Offset from the start of the containing input section.
   uint32_t inSecOff;
   uint32_t live : 1;
+  // Only set if deduplicating literals
   uint32_t hash : 31;
   // Offset from the start of the containing output section.
   uint64_t outSecOff = 0;
 
   StringPiece(uint64_t off, uint32_t hash)
       : inSecOff(off), live(!config->deadStrip), hash(hash) {}
 };
 
public:
   bool isLive(uint64_t off) const override { return getStringPiece(off).live; }
   void markLive(uint64_t off) override { getStringPiece(off).live = true; }
   // Find the StringPiece that contains this offset.
   StringPiece &getStringPiece(uint64_t off);
   const StringPiece &getStringPiece(uint64_t off) const;
   // Split at each null byte.
   void splitIntoPieces();
 
-  // Returns i'th piece as a CachedHashStringRef. This function is very hot when
-  // string merging is enabled, so we want to inline.
   LLVM_ATTRIBUTE_ALWAYS_INLINE
-  llvm::CachedHashStringRef getCachedHashStringRef(size_t i) const {
+  StringRef getStringRef(size_t i) const {
     size_t begin = pieces[i].inSecOff;
     size_t end =
         (pieces.size() - 1 == i) ? data.size() : pieces[i + 1].inSecOff;
-    return {toStringRef(data.slice(begin, end - begin)), pieces[i].hash};
+    return toStringRef(data.slice(begin, end - begin));
+  }
+
+  // Returns i'th piece as a CachedHashStringRef. This function is very hot when
+  // string merging is enabled, so we want to inline.
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  llvm::CachedHashStringRef getCachedHashStringRef(size_t i) const {
+    assert(config->dedupLiterals);
+    return {getStringRef(i), pieces[i].hash};
   }
 
   static bool classof(const InputSection *isec) {
     return isec->kind() == CStringLiteralKind;
   }
 
   std::vector<StringPiece> pieces;
 };

lld/MachO/InputSection.cpp

 //===- InputSection.cpp ---------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputSection.h"
+#include "Config.h"
 #include "InputFiles.h"
 #include "OutputSegment.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "UnwindInfoSection.h"
 #include "Writer.h"
 #include "lld/Common/Memory.h"

 void CStringInputSection::splitIntoPieces() {
   size_t off = 0;
   StringRef s = toStringRef(data);
   while (!s.empty()) {
     size_t end = s.find(0);
     if (end == StringRef::npos)
       fatal(toString(this) + ": string is not null terminated");
     size_t size = end + 1;
-    pieces.emplace_back(off, xxHash64(s.substr(0, size)));
+    uint32_t hash = config->dedupLiterals ? xxHash64(s.substr(0, size)) : 0;
+    pieces.emplace_back(off, hash);
     s = s.substr(size);
     off += size;
   }
 }
 
 StringPiece &CStringInputSection::getStringPiece(uint64_t off) {
   if (off >= data.size())
     fatal(toString(this) + ": offset is outside the section");

lld/MachO/SyntheticSections.h

public:
   void finalize() override;
   void writeTo(uint8_t *buf) const override;
 
 private:
   llvm::SmallString<261> xarPath;
   uint64_t xarSize;
 };
 
-class CStringSection final : public SyntheticSection {
+class CStringSection : public SyntheticSection {
 public:
   CStringSection();
   void addInput(CStringInputSection *);
-  uint64_t getSize() const override { return builder.getSize(); }
-  void finalizeContents();
+  uint64_t getSize() const override { return size; }
+  virtual void finalizeContents();
   bool isNeeded() const override { return !inputs.empty(); }
-  void writeTo(uint8_t *buf) const override { builder.write(buf); }
+  void writeTo(uint8_t *buf) const override;
 
   std::vector<CStringInputSection *> inputs;
 
 private:
+  uint64_t size;
+};
+
+class DeduplicatedCStringSection final : public CStringSection {
+public:
+  DeduplicatedCStringSection();
+  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;
 };
 
 /*
  * This section contains deduplicated literal values. The 16-byte values are
  * laid out first, followed by the 8- and then the 4-byte ones.
  */
 class WordLiteralSection final : public SyntheticSection {

lld/MachO/SyntheticSections.cpp

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) {
+  flags = S_CSTRING_LITERALS;
+}
+
+void CStringSection::addInput(CStringInputSection *isec) {
+  isec->parent = this;
+  inputs.push_back(isec);
+  if (isec->align > align)
+    align = isec->align;
+}
+
+void CStringSection::writeTo(uint8_t *buf) const {
+  for (const CStringInputSection *isec : inputs) {
+    for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
+      if (!isec->pieces[i].live)
+        continue;
+      StringRef string = isec->getStringRef(i);
+      memcpy(buf + isec->pieces[i].outSecOff, string.data(), string.size());
+    }
+  }
+}
+
+void CStringSection::finalizeContents() {
+  uint64_t offset = 0;
+  for (CStringInputSection *isec : inputs) {
+    for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
+      if (!isec->pieces[i].live)
+        continue;
+      uint32_t pieceAlign = MinAlign(isec->pieces[i].inSecOff, align);
+      offset = alignTo(offset, pieceAlign);
+      isec->pieces[i].outSecOff = offset;
+      isec->isFinal = true;
+      StringRef string = isec->getStringRef(i);
+      offset += string.size();
+    }
+  }
+  size = offset;
+}
 // 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.
-CStringSection::CStringSection()
-    : SyntheticSection(segment_names::text, section_names::cString),
-      builder(StringTableBuilder::RAW, /*Alignment=*/16) {
-  align = 16;
-  flags = S_CSTRING_LITERALS;
-}
+DeduplicatedCStringSection::DeduplicatedCStringSection()
+    : builder(StringTableBuilder::RAW, /*Alignment=*/16) {}
 
-void CStringSection::addInput(CStringInputSection *isec) {
-  isec->parent = this;
-  inputs.push_back(isec);
-}
-
-void CStringSection::finalizeContents() {
+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));
 
   // Fix the string table content. After this, the contents will never change.

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>();
-  in.cStringSection = config->dedupLiterals ? make<CStringSection>() : nullptr;
+  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/dead-strip-align.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
+# RUN: %lld -lSystem -o %t.out %t.o -dead_strip
+# RUN: llvm-otool -l %t.out | FileCheck --check-prefix=SECT %s
+# RUN: llvm-otool -vs __TEXT __cstring %t.out | FileCheck %s
+
+# SECT:      sectname __cstring
+# SECT-NEXT: segname __TEXT
+# SECT-NEXT: addr
+# SECT-NEXT: size
+# SECT-NEXT: offset
+# SECT-NEXT: align 2^4 (16)
+
+# CHECK: 0 \303Q043\005\376\334\272\230vT2\020\001
+# CHECK: 8 def
+
+.section __TEXT,__cstring,cstring_literals
+.globl _foo
+_foo:  # Dead. External, has symbol table entry, gets stripped.
+  .asciz "asdf"
+
+.globl _hi
+_hi:
+  .asciz "hi" # External, has symbol table entry.
+
+.p2align 4
+L_internal_aligned_16: # Has no symbol table entry.
+  .asciz "\303Q043\005\376\334\272\230vT2\020\001"
+
+L_internal_nonaligned:
+  .asciz "abc"
+
+.p2align 3
+L_internal_aligned_8:
+  .asciz "def"
+
+.text
+.globl _main
+_main:
+  movq _hi(%rip), %rax
+  movq L_internal_nonaligned(%rip), %rax
+  movq L_internal_aligned_8(%rip), %rax
+  movaps L_internal_aligned_16(%rip), %xmm0
+  retq
+
+.subsections_via_symbols

lld/test/MachO/subsections-section-relocs.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: %lld -o %t/test %t/test.o -order_file %t/order-file
-# RUN: llvm-objdump --section-headers -d --no-show-raw-insn %t/test | FileCheck %s
-# CHECK-LABEL: Sections:
-# CHECK:       __cstring {{[^ ]*}} {{0*}}[[#%x, CSTRING_ADDR:]]
-# CHECK-LABEL: Disassembly of section __TEXT,__text:
-## L._str should end up at CSTRING_ADDR + 4, and leaq is 7 bytes long so we
-## have RIP = ADDR + 7
-# CHECK:       [[#%x, ADDR:]]: leaq
-# CHECK-SAME:    [[#%u, CSTRING_ADDR + 4 - ADDR - 7]](%rip), %rsi {{.*}} <_bar_str+0x4>
-
-# RUN: llvm-readobj --string-dump=__cstring %t/test | FileCheck %s --check-prefix=STRINGS
-# STRINGS: bar
-# STRINGS: Private symbol
-# STRINGS: foo
-
-#--- order-file
-_bar_str
-_foo_str
-
-#--- test.s
-.text
-.globl _main, _foo_str, _bar_str
-
-_main:
-  leaq L_.str(%rip), %rsi
-  mov $0, %rax
-  ret
-
-.section __TEXT,__cstring
-_foo_str:
-  .asciz "foo"
-
-_bar_str:
-  .asciz "bar"
-
-## References to this generate a section relocation
-## N.B.: ld64 doesn't actually reorder symbols in __cstring based on the order
-##       file. Our implementation only does does so if --no-literal-merge is
-##       specified. I'm not sure how else to test section relocations that
-##       target an address inside a relocated symbol: using a non-__cstring
-##       section would cause llvm-mc to emit a symbol relocation instead using
-##       the nearest symbol. It might be more consistent for LLD to disable
-##       symbol-based cstring reordering altogether and leave this functionality
-##       untested, at least until we find a real-world use case...
-L_.str:
-  .asciz "Private symbol"
-
-.subsections_via_symbols