[lld-macho] Sort data-in-code entries

[BertalanD]

Summary

Previously, we would add entries to DataInCodeSection in the order they
appeared in input files. Because of this, entries would not be sorted if
sections were reordered due to e.g. -order_file or call graph profile
sorting.

This commit also fixes an incorrect assertion. The original assertion
from D103006 used to check that data-in-code entries are sorted in the
input objects -- likely because we use binary search on that data. In
D115556, the assertion was moved into collectDataInCodeEntries, but
the checked variable's name was not changed, so it ended up checking the
final contents of the DataInCodeSection. While this section is
guaranteed to be sorted as of this commit, we should still check that
inputs are not malformed.

This fixes a crash when building LLVM with PGO using an asserts build of
LLD as the linker.

Numbers for linking the Chromium Framework reproducer from #48001, which
has 6829 data-in-code entries:

x before
+ after
    N           Min           Max        Median           Avg        Stddev
x  20     2.1076453     2.3059683     2.1132485     2.1350302   0.049905767
+  20     2.1069031     2.3915262       2.14465     2.1728429   0.084065898
No difference proven at 95.0% confidence

[thakis]

Thanks for looking into this!

Is just removing the assert the right thing? It kind of makes sense to require the data in code table in the output to be sorted too, so that tools can binary sort in _it_. With ld, it looks like it is sorted (with first.o, second.o, third.o, order.txt as in your test, except compiled like clang -c first.s and hence on my machine arm64):

% out/gn/bin/clang first.o second.o third.o -Wl,-order_file,order.txt -isysroot $(xcrun -show-sdk-path) -shared 
ld: warning: arm64 function not 4-byte aligned: _second from second.o
ld: warning: arm64 function not 4-byte aligned: _first from first.o
ld: warning: arm64 function not 4-byte aligned: _third from third.o
% otool -G a.out                                                                                                
a.out:
Data in code table (3 entries)
offset     length kind
0x00003fac      4 0x0004
0x00003fb0      4 0x0004
0x00003fb4      4 0x0004

These are sorted!

Now, lld with this patch:

% out/gn/bin/clang first.o second.o third.o -Wl,-order_file,order.txt -isysroot $(xcrun -show-sdk-path) -shared -fuse-ld=lld
% otool -G a.out                                                                                                            
a.out:
Data in code table (3 entries)
offset     length kind
0x0000027c      4 0x0004
0x00000278      4 0x0004
0x00000280      4 0x0004

These are not sorted!

So maybe the problem isn't the assert, but that our construction of the DIC table doesn't always fulfill the assert?

[BertalanD]

It kind of makes sense to require the data in code table in the output to be sorted too, so that tools can binary sort in _it_.

Right, it looks like ld64 explicitly sorts its contents (https://github.com/apple-oss-distributions/ld64/blob/dbf8f7feb5579761f1623b004bd468bdea7c6225/src/ld/LinkEdit.hpp#L2112), so we should do the same. At the same time, I do not have any information about what tools use data-in-code tables and in what way, so sorting might end up being unnecessary work.

I'll update this diff to sort the entries alongside fixing the faulty assertion.

[BertalanD]

Sort DataInCodeSection's contents as suggested by thakis.

[int3]

Thanks!

lld/MachO/SyntheticSections.cpp

966

add a comment mentioning that ld64 emits the table in sorted order too? could even link directly to https://reviews.llvm.org/D133581#3781121

[thakis]

(The below is mostly note-to-self and maybe interesting to others -- nothing actionable. I'd like to look into how to produce data-in-code tables on x86_64 some more. The very last line has a question for you, though.)

In D133581#3782233, @BertalanD wrote:

Right, it looks like ld64 explicitly sorts its contents (https://github.com/apple-oss-distributions/ld64/blob/dbf8f7feb5579761f1623b004bd468bdea7c6225/src/ld/LinkEdit.hpp#L2112), so we should do the same. At the same time, I do not have any information about what tools use data-in-code tables and in what way

That's a great question.

otool -tV (and llvm-otool -tV and the corresponding llvm-objdump invocation) do make use of it:

 % otool -tV llvm/test/Object/Inputs/macho-data-in-code.macho-thumbv7
...
00000012	    bd80	pop	{r7, pc}
00000014	00000038	.long 56	@ KIND_DATA

For llvm-objdump, this was added in 273ae01b0353 (https://reviews.llvm.org/rG273ae01b0353). Since vanilla otool does it too, I suppose there's code in cctools and maybe something else in cctools might use it? Huh, looks like it's in arm_disasm.c in cctools (print_data_in_code). For llvm-objdump, the code for this is _in_ the llvm-objdump tool code, so programs built on top of LLVM's libraries won't pick this up for free. The llvm-objdump code does explicitly sort the table.

But as far as I can tell, nothing else looks at this table. These tools all don't look at data-in-code as far as I can tell:

• lldb (tried it, see below)
• radare2 (only looked through source code)
• Ghidra (only looked through source code)
• Hopper (tried it with bar.o below; no source code for this, though)

It is hard to produce data-in-code tables on arm64!

On arm32, it's fairly easy with --target=arm-apple-ios but not with --target=armv7-apple-ios (and lld doesn't support 32-bit links anyways) -- compiling a file containing e.g. g(0x10001); or a simple switch statement produces data-in-code entries.

On arm64, I haven't managed to do it without inline asm. With inline asm, asm("ldr x0,=0x10001"); does cause creation of data-in-code.

As mentioned above, otool only interprets data-in-code for 32-bit arm, but llvm-otool can handle it in 64-bit arm too:

 % cat bar.cc
void as() { asm("ldr x0,=0x10001"); }

% out/gn/bin/llvm-otool -tV bar.o 
bar.o:
Contents of (__TEXT,__text) section
__Z2asv:
0000000000000000	ldr	x0, #0x8
0000000000000004	ret
0000000000000008	.long 65537	@ KIND_DATA
000000000000000c	.long 0	@ KIND_DATA

% otool -tV bar.o 
bar.o:
(__TEXT,__text) section
__Z2asv:
0000000000000000	ldr	x0, #0x8
0000000000000004	ret
0000000000000008	.long	0x00010001
000000000000000c	udf	#0x0

% lldb bar.o
(lldb) target create "bar.o"
Current executable set to '/Users/thakis/src/llvm-project/bar.o' (arm64).
(lldb) disas -n _Z2asv
bar.o`as:
bar.o[0x0] <+0>:  ldr    x0, #0x8                  ; <+8>
bar.o[0x4] <+4>:  ret    
bar.o[0x8] <+8>:  .long  0x00010001                ; unknown opcode
bar.o[0xc] <+12>: udf    #0x0

I didn't manage to trigger this at all on x86_64 code. But given we hit this assert in lld when doing a bootstrap build of LLVM on x86_64, it has to be possible to get this for fairly normal code on x86_64 :) % otool -G out/gn/bin/* | grep -v offset | grep -v out | grep -v 0 on my build dir on my arm mac doesn't find anything. I don't have my intel machine with me at the moment.

so sorting might end up being unnecessary work.

Does it take noticeable amounts of time?

[thakis]

Here's one way to trigger data-in-code on x86_64:

% cat bar.cc
__attribute__((noinline)) inline int sw(int i) {
  switch (i) {
  case 0: return 3443;
  case 1: return 3453;
  case 2: return 3353;
  case 3: return 4353;
  default: return -1;
  }
}

void ref() {
  sw(2);
}

% clang -c bar.cc  --target=x86_64-apple-darwin

% otool -G bar.o                                
bar.o:
Data in code table (1 entries)
offset     length kind
0x00000078     16 0x0004

% out/gn/bin/llvm-otool -tV bar.o
...
0000000000000078	.long 4294967236	@ KIND_JUMP_TABLE32

(cctools otool again doesn't handle this.)

Need to carefully pick number of cases in switch and whatnot to make http://llvm-cs.pcc.me.uk/include/llvm/CodeGen/TargetLowering.h#1032 (isSuitableForJumpTable impl) and http://llvm-cs.pcc.me.uk/lib/CodeGen/SwitchLoweringUtils.cpp#64 (MinJumpTableEntries comparison in SwitchCG::SwitchLowering::findJumpTables) happy – then http://llvm-cs.pcc.me.uk/lib/CodeGen/SwitchLoweringUtils.cpp#85 (isSuitableForJumpTable check in SwitchCG::SwitchLowering::findJumpTables) will trigger and we'll end up with a jump table.

Also needs to be in an inline function, else the data just goes in __TEXT,__const due to http://llvm-cs.pcc.me.uk/lib/Target/TargetLoweringObjectFile.cpp#291 (F.isWeakForLinker check in TargetLoweringObjectFile::shouldPutJumpTableInFunctionSection)

That explains why we see the assert on x86_64.

[thakis]

As for why we don't hit this on AArch64: http://llvm-cs.pcc.me.uk/lib/Target/AArch64/AArch64AsmPrinter.cpp#686 AArch64AsmPrinter::emitJumpTableInfo overrides AsmPrinter::emitJumpTableInfo, and the override doesn't call OutStreamer->emitDataRegion(MCDR_DataRegionJT32); for whatever reason. It probably should?

But that explains why we _don't_ currently see the assert on arm64.

With that, I think everything's explained :)

[thakis]

Also, this fixes the last known assert in https://bugs.chromium.org/p/chromium/issues/detail?id=1265937 (using lld as host linker when making chromium's clang package), probably good to reference this from here.

[BertalanD]

Thank you for the write-up, it was very interesting!

Does it take noticeable amounts of time?

See the benchmark posted in the summary. Sorting 6000 8-byte data_in_code_entry structs seems to have a negligible overhead.

I'll commit this with the requested comment change in a moment. I will de-templatize this code collectDataInCodeEntries, and move it into DataInCodeSection::finalizeContents() in a follow-up commit.

[thakis]

In D133581#3786416, @thakis wrote:

As for why we don't hit this on AArch64: http://llvm-cs.pcc.me.uk/lib/Target/AArch64/AArch64AsmPrinter.cpp#686 AArch64AsmPrinter::emitJumpTableInfo overrides AsmPrinter::emitJumpTableInfo, and the override doesn't call OutStreamer->emitDataRegion(MCDR_DataRegionJT32); for whatever reason. It probably should?

But that explains why we _don't_ currently see the assert on arm64.

With that, I think everything's explained :)

Follow-up to this: After D113576, llvm _always_ puts jump tables in __TEXT,__const on aarch64, so it never shows up in disassembly -- even for inline functions. (Things then rely on -dead_strip to remove the unused data from the jump tables references from non-prevailing inlines, instead of them not being linked in to the binary in the first place.) clang coming with the version of Xcode I'm using doesn't have that change yet as far as I can tell, so I didn't notice this immediately.

lld/MachO/SyntheticSections.h

public:
 
   bool hasWeakSymbol = false;
 
 private:
   TrieBuilder trieBuilder;
   size_t size = 0;
 };
 
-// Stores 'data in code' entries that describe the locations of
-// data regions inside code sections.
+// Stores 'data in code' entries that describe the locations of data regions
+// inside code sections. This is used by llvm-objdump to distinguish jump tables
+// and stop them from being disassembled as instructions.
 class DataInCodeSection final : public LinkEditSection {
 public:
   DataInCodeSection();
   void finalizeContents() override;
   uint64_t getRawSize() const override {
     return sizeof(llvm::MachO::data_in_code_entry) * entries.size();
   }
   void writeTo(uint8_t *buf) const override;

lld/MachO/SyntheticSections.cpp

static std::vector<MachO::data_in_code_entry> collectDataInCodeEntries() {
   for (const InputFile *inputFile : inputFiles) {
     if (!isa<ObjFile>(inputFile))
       continue;
     const ObjFile *objFile = cast<ObjFile>(inputFile);
     ArrayRef<MachO::data_in_code_entry> entries = objFile->getDataInCode();
     if (entries.empty())
       continue;
 
-    assert(is_sorted(dataInCodeEntries, [](const data_in_code_entry &lhs,
-                                           const data_in_code_entry &rhs) {
+    assert(is_sorted(entries, [](const data_in_code_entry &lhs,
       return lhs.offset < rhs.offset;
     }));
     // For each code subsection find 'data in code' entries residing in it.
     // Compute the new offset values as
     // <offset within subsection> + <subsection address> - <__TEXT address>.
     for (const Section *section : objFile->sections) {
       for (const Subsection &subsec : section->subsections) {
         const InputSection *isec = subsec.isec;
for (const Section *section : objFile->sections) {
              it != end && it->offset + it->length <= endAddr; ++it)
           dataInCodeEntries.push_back(
               {static_cast<uint32_t>(isec->getVA(it->offset - beginAddr) -
                                      in.header->addr),
                it->length, it->kind});
       }
     }
   }
+
+  // ld64 emits the table in sorted order too.
+  llvm::sort(dataInCodeEntries,
+             [](const data_in_code_entry &lhs, const data_in_code_entry &rhs) {
+               return lhs.offset < rhs.offset;
+             });
   return dataInCodeEntries;
 }
 
 void DataInCodeSection::finalizeContents() {
   entries = target->wordSize == 8 ? collectDataInCodeEntries<LP64>()
                                   : collectDataInCodeEntries<ILP32>();
 }
 

lld/test/MachO/data-in-code-section-ordering.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+
+## Check that data-in-code information is sorted even if
+## sections are reordered compared to the input order.
+
+# RUN: sed -e s/SYM/_first/ %t/input.s | \
+# RUN:   llvm-mc -filetype=obj --triple=x86_64-apple-darwin -o %t/first.o
+# RUN: sed -e s/SYM/_second/ %t/input.s | \
+# RUN:   llvm-mc -filetype=obj --triple=x86_64-apple-darwin -o %t/second.o
+# RUN: sed -e s/SYM/_third/ %t/input.s | \
+# RUN:   llvm-mc -filetype=obj --triple=x86_64-apple-darwin -o %t/third.o
+# RUN: %lld -dylib -lSystem -order_file %t/order.txt %t/first.o %t/second.o %t/third.o -o %t/out
+# RUN: llvm-objdump --macho --syms %t/out > %t/dump.txt
+# RUN: llvm-objdump --macho --data-in-code %t/out >> %t/dump.txt
+# RUN: FileCheck %s < %t/dump.txt
+
+# CHECK-LABEL: SYMBOL TABLE:
+# CHECK-DAG:   [[#%x, SECOND:]] g     F __TEXT,__text _second
+# CHECK-DAG:   [[#%x, FIRST:]]  g     F __TEXT,__text _first
+# CHECK-DAG:   [[#%x, THIRD:]]  g     F __TEXT,__text _third
+
+# CHECK-LABEL: Data in code table (3 entries)
+# CHECK-NEXT:  offset              length kind
+# CHECK-NEXT:  0x[[#%.8x, SECOND]] 4      JUMP_TABLE32
+# CHECK-NEXT:  0x[[#%.8x, FIRST]]  4      JUMP_TABLE32
+# CHECK-NEXT:  0x[[#%.8x, THIRD]]  4      JUMP_TABLE32
+
+#--- order.txt
+_second
+_first
+_third
+
+#--- input.s
+.globl SYM
+SYM:
+.data_region jt32
+.long 0
+.end_data_region