This is an archive of the discontinued LLVM Phabricator instance.

[lld-macho] Use DO_BIND_ADD_ADDR_IMM_SCALED for bind opcodes
ClosedPublic

Authored by thevinster on Jul 15 2021, 10:33 PM.

Details

Summary

Implement pass 3 of bind opcodes from ld64 (which supports both 32-bit and 64-bit).
Pass 3 implementation condenses BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB opcode
to BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED. This change is already behind an
O2 flag so it shouldn't impact current performance. I verified ld64's output with x86_64 LLD
and they were both emitting the same optimized bind opcodes (although in a slightly different
order). Tested with arm64_32 LLD and compared that with x86 LLD that the order of the bind
opcodes are the same (offset values are different which should be expected).

Diff Detail

Event Timeline

thevinster created this revision.Jul 15 2021, 10:33 PM
Herald added a reviewer: gkm. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
thevinster requested review of this revision.Jul 15 2021, 10:33 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 15 2021, 10:33 PM
int3 added inline comments.Jul 15 2021, 10:38 PM
lld/MachO/SyntheticSections.cpp
367–368

can we have a comment explaining how BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED works, and where the 15 and sizeof(uint64_t) is coming from?

thevinster added inline comments.Jul 15 2021, 10:39 PM
lld/MachO/SyntheticSections.cpp
367

I believe ld64 switches off the type based on whether it operates on a 32-bit or a 64-bit. I didn't get a chance to verify it because LLD doesn't seem to support i386 (https://github.com/llvm/llvm-project/blob/main/lld/MachO/Driver.cpp#L700-L711).

thevinster marked an inline comment as not done.Jul 15 2021, 10:40 PM
thevinster added inline comments.
lld/MachO/SyntheticSections.cpp
367–368

That was quick! Will add a comment about the 15. As far as the sizeof(uint64_t), I wrote a comment above describing that situation.

int3 added inline comments.Jul 15 2021, 10:45 PM
lld/MachO/SyntheticSections.cpp
367

I'm confused as to why LLD not supporting i386 matters for testing ld64's behavior. llvm-mc can emit i386 object files that we can pass to ld64...

thevinster marked an inline comment as not done.Jul 15 2021, 10:50 PM
thevinster added inline comments.
lld/MachO/SyntheticSections.cpp
367

I get the following error when trying to pass an i386 object file to LLD using x86_64 arch. ld64.lld: error: /Users/leevince/local/llvm-project/build/Debug/tools/lld/test/MachO/Output/bind-opcodes.s.tmp/foo.o has architecture i386 which is incompatible with target architecture x86_64. I'm unsure how to go about this without having to support i386.

Address comments, split logic by 32-bit or 64-bit, clang-format, tests

thevinster edited the summary of this revision. (Show Details)Jul 16 2021, 5:09 PM
thevinster edited the summary of this revision. (Show Details)Jul 16 2021, 5:10 PM
thevinster added inline comments.
lld/MachO/SyntheticSections.cpp
367

Spoken offline - tested 32-bit arch using arm64_32, and used that as comparison with x86_64.

367–368

I switched the use of 15 to BIND_IMMEDIATE_MASK which I think should be enough to cover adding the extra comment, but I'm happy to add it if it's still confusing to readers.

lld/test/MachO/bind-opcodes.s
1

This file is pretty messy and hard to read. So I'll try to condense what I did here.
1/ In order to run both 64-bit tests and 32-bit tests in one file, I had to separate the suffix the input and output with the arch.
2/ Nothing changed with llvm-objdump. It was merely a forklift from the bottom to the top. There isn't a corresponding one for the arm64_32. I'm not exactly familiar with what it does, but I'm happy to add it if it provides value.
3/ In order to satisfy the linker, I had to switch the use of quad to int otherwise I get relocation errors. The order of the bind opcodes between 32-bit and 64-bit are the same (with slightly offsets)
4/ CHECK are in its own separate files now in order to isolate between different arch.

int3 added inline comments.Jul 17 2021, 12:46 AM
lld/MachO/SyntheticSections.cpp
365–366

the ternary is unnecessary, offsetWidth is just target->wordSize :)

also, I think offsetWidth is kind of a misleading name... pointerSize is probably more apt. Or we could just use target->wordSize directly.

I think I understand the motivation behind this opcode design: Since every binding is the size of one pointer, the next binding must be at least wordSize away. Most likely it's some multiple of wordSize away (if there are multiple intervening pointers). Hence the scaling by pointer size. (Might be worth to write something like this as a comment)

369

how about p->data / offsetWidth <= BIND_IMMEDIATE_MASK, to mirror the assignment below?

372
lld/test/MachO/bind-opcodes.s
1

I think we can make it less messy :)

1: yeah this makes sense
2: dumping the bind table is basically a sanity check: it decodes the bind opcodes into an easy-to-read form so we can verify that we encoded the right things. I think it's worth adding for 32-bit as well, but we can be clever and reuse the same code (see below)
3: I think we can reuse the same code. I haven't tested this but I think something like it should work:

.ifdef PTR64
.macro ptr val
  .quad val
.endm
.endif

.ifdef PTR32
.macro ptr val
  .int val
.endm
.endif

ptr _foo
ptr _bar
...

PTR64 and PTR32 will have to be defined as part of llvm-mc's invocation. See https://github.com/llvm/llvm-project/blob/main/llvm/test/DebugInfo/X86/dwarfdump-header-64.s for an example.
4: FileCheck takes a --check-prefix argument, so we can put the checks in the same file.

15–20

something like this should allow reusing the check across both archs

(see 'Numeric Substitutions' in the FileCheck manual for details)

29

you can just do %lld -arch arm64_32, the later arch will override the earlier one. no need to define another substitution

thevinster marked 5 inline comments as done.Jul 19 2021, 2:09 AM
thevinster added inline comments.
lld/MachO/SyntheticSections.cpp
369

I changed it to p->data / target->wordSize < BIND_IMMEDIATE_MASK. I removed the equals comparison because when dyld uncompacts, it seems to add an extra sizeof(intptr_t).

See https://opensource.apple.com/source/dyld/dyld-852/src/ImageLoaderMachOCompressed.cpp.auto.html and search for address += immediate*sizeof(intptr_t) + sizeof(intptr_t);

lld/test/MachO/bind-opcodes.s
1

All of them make sense and have been fixed. The file looks a lot cleaner now :)

thevinster marked 2 inline comments as done.

Address more comments

int3 accepted this revision.Jul 19 2021, 8:38 AM

Thanks!

lld/MachO/SyntheticSections.cpp
369

I think the previous implementation was the right one. The DO_BIND opcode itself adds a sizeof(intptr_t), which is probably why dyld is doing that.

From http://www.m4b.io/reverse/engineering/mach/binaries/2015/03/29/mach-binaries.html 's description of DO_BIND:

Push the current record onto the "import stack", and then increment the current record's address offset by the size of the platform pointer (32 or 64 bit)

It would be good to have a test case that covers this edge case :)

This revision is now accepted and ready to land.Jul 19 2021, 8:38 AM
int3 added a comment.Jul 19 2021, 1:55 PM

one nit about the commit title / description: there are lots of opcodes with immediates, I think it would be clearer to mention DO_BIND_ADD_ADDR_IMM_SCALED specifically in the title. Also "Implement pass 3 of bind opcodes from ld64" should be followed by a short description of what pass 3 does -- we shouldn't expect future readers to have to look it up :)

lld/test/MachO/bind-opcodes.s
1

almost forgot about this :) we need it now that we're building arm binaries

thevinster retitled this revision from [lld-macho] Use immediate encodings for bind opcodes to [lld-macho] Use DO_BIND_ADD_ADDR_IMM_SCALED for bind opcodes.Jul 19 2021, 2:50 PM
thevinster edited the summary of this revision. (Show Details)
thevinster marked 3 inline comments as done.Jul 19 2021, 2:54 PM

one nit about the commit title / description: there are lots of opcodes with immediates, I think it would be clearer to mention DO_BIND_ADD_ADDR_IMM_SCALED specifically in the title. Also "Implement pass 3 of bind opcodes from ld64" should be followed by a short description of what pass 3 does -- we shouldn't expect future readers to have to look it up :)

Done.

lld/MachO/SyntheticSections.cpp
369

Re-capping offline convo. In ld64's implementation, it uses "<" instead of "<=". It makes more sense to keep the same behavior to prevent any unknown deviations from ld64. It may be a typo on ld64, but this will prevent unknown mysterious bugs down the road.

thevinster marked an inline comment as done.

Add comments for clarity and address minor comments

MaskRay reopened this revision.EditedJul 19 2021, 6:15 PM
MaskRay added a subscriber: MaskRay.

Reverted by 88e2268a344a0ab3df455af08f32c2c354ea55a4

for (BindIR *p = &opcodes[0]; p->opcode != BIND_OPCODE_DONE; ++p) { has a heap-buffer-overflow with test/MachO/bind-opcodes.s

-DLLVM_USE_SANITIZER=Address check-lld-macho to reproduce.

This revision is now accepted and ready to land.Jul 19 2021, 6:15 PM
MaskRay requested changes to this revision.Jul 19 2021, 6:15 PM
This revision now requires changes to proceed.Jul 19 2021, 6:15 PM
thevinster updated this revision to Diff 359989.EditedJul 19 2021, 7:43 PM

Fixing ASAN

In D106128, buffer overflow was detected when incrementing BindIR pointers. This would
most likely not happen in an ideal world, but switching it to array indexing
is safer.

Ran with -DLLVM_USE_SANITIZER=Address and check-lld-macho.

thevinster retitled this revision from [lld-macho] Use DO_BIND_ADD_ADDR_IMM_SCALED for bind opcodes to Recommit "[lld-macho] Use DO_BIND_ADD_ADDR_IMM_SCALED for bind opcodes".Jul 19 2021, 7:47 PM
thevinster edited the summary of this revision. (Show Details)
thevinster retitled this revision from Recommit "[lld-macho] Use DO_BIND_ADD_ADDR_IMM_SCALED for bind opcodes" to [lld-macho] Use DO_BIND_ADD_ADDR_IMM_SCALED for bind opcodes.
thevinster edited the summary of this revision. (Show Details)
int3 accepted this revision.Jul 20 2021, 4:50 AM

Fix looks good but can we figure out how it was happening in the first place? I would guess that we were running optimizeOpcodes on an empty vector, but I'm not sure how that would happen in the given test...

lld/MachO/SyntheticSections.cpp
369

I think this can be a for-range loop

thevinster marked an inline comment as done.Jul 20 2021, 10:49 AM

Fix looks good but can we figure out how it was happening in the first place? I would guess that we were running optimizeOpcodes on an empty vector, but I'm not sure how that would happen in the given test...

We assumed that the BIND_OPCODE_DONE would exist in the vector but it actually doesn't. It actually never gets stored in the vector and is just emitted after everything is optimized. Printing out the opcodes as well shows that BIND_OPCODE_DONE never existed. Now, why this wasn't caught in testing is that this pass happens on specific checks. Sooner or later, it will randomly encounter the an opcode of 0 (by random chance) and exit the loop. The size and contents of the vector are still unchanged so testing without ASAN continued to show correct results.

lld/MachO/SyntheticSections.cpp
369

Done. Re-tested with ASAN. Everything looks good :)

thevinster marked an inline comment as done.

use for range loop

int3 added a comment.Jul 20 2021, 11:06 AM

It actually never gets stored in the vector and is just emitted after everything is optimized.

D'oh, that makes sense :)

MaskRay accepted this revision.EditedJul 20 2021, 11:47 AM

Some patterns may not exist in the real world but it'd be good to think of such scenarios and don't crash the linker.
buffer overrun is worse, because it makes the linker vulnerable.

This revision is now accepted and ready to land.Jul 20 2021, 11:47 AM