This is an archive of the discontinued LLVM Phabricator instance.

[LLD][ELF][ARM] Refactor inBranchRange to use addend for PC Bias
ClosedPublic

Authored by peter.smith on Feb 26 2021, 6:04 AM.

Details

Summary

In AArch32 ARM, the PC reads two instructions ahead of the currently executiing instruction. This evaluates to 8 in ARM state and 4 in Thumb state. Branch instructions on AArch32 compensate for this by subtracting the PC bias from the addend. For a branch to symbol this will result in an addend of -8 in ARM state and -4 in Thumb state.

The existing ARM Target::inBranchRange function accounted for this implict addend within the function meaning that if the addend were to be taken into account by the caller then it would be double counted. This complicates the interface for all Targets as callers wanting to account for addends had to account for the ARM PC-bias.

In certain situations such as: https://github.com/ClangBuiltLinux/linux/issues/1305 the PC-bias compensation code didn't match up. In particular normalizeExistingThunk() didn't put the PC-bias back in as Arm thunks did not store the addend.

The simplest fix for the problem is to add the PC bias in normalizeExistingThunk when restoring the addend. However I think it is worth refactoring the Arm inBranchRange implementation so that fewer calls to getPCBias are needed for other Targets. I wasn't able to remove getPCBias completely but hopefully the Relocations.cpp code is simpler now.

In principle a test could be written to replicate the linux kernel build failure but I wasn't able to reproduce with a small example that I could build up from scratch.

Fixes https://github.com/ClangBuiltLinux/linux/issues/1305

Diff Detail

Event Timeline

peter.smith created this revision.Feb 26 2021, 6:04 AM
peter.smith requested review of this revision.Feb 26 2021, 6:04 AM

Thanks for working on this! inBranchRange looks simpler now.

lld/ELF/Arch/ARM.cpp
359

Nit: add a period after a complete sentence.

391

Thanks for the clean-up!

I stared at this piece code a couple of times and worried that this could be off by a few bytes but was not able to comprehend it.

lld/ELF/Relocations.cpp
1937

This probably needs a test (similar to D70637) to test sharing, even if it is difficult to construct a test exercising the range limit.

MaskRay accepted this revision.Feb 27 2021, 12:02 AM
This revision is now accepted and ready to land.Feb 27 2021, 12:02 AM
MaskRay added inline comments.Feb 27 2021, 12:30 AM
lld/ELF/Arch/ARM.cpp
301

IIUC a is usually -8, so dst+a-branchAddr is the value to be encoded. So this simplifies understanding. inBranchRange can just use the regular [-2**n, 2**n) range instead of doing some compensation.

lld/ELF/Relocations.cpp
1937

Perhaps the comment can say that keyAddend is usually 0, even on ARM.

peter.smith marked an inline comment as done.Mar 1 2021, 3:22 AM

Thanks, I'll upload another patch.

I can write a test case for thunk reuse. The linux kernel problem is complicated as it needs several passes to populate the table in such a way that an error message will be produced:
pass 0:

  • Add thunks round 1 (all thunks are added with rel.addend + getPCBias(rel.type) = 0

pass N:

  • normalizeExistingThunk invalidates some calls to thunks, their rel.addend is set to 0
  • Thunks are added again with rel.addend + getPCBias(rel.type) = -8. By definition no match with any existing thunk as key addend is -8 and all previous thunks will have key addend 0.

pass N + M:

  • normalizeExistingThunk invalidates some calls to thunks, their rel.addend is set to 0
  • One of the invalidated calls matches an existing thunk as we now have existing thunks added with key addend -8 (from normalizeExistingThunks), we match one of these existing thunks yet we can be up to 8 bytes out of range due to the rel.addend being 0 in the range check.
lld/ELF/Relocations.cpp
1937

I've made a specific test case that tests this line. There is an existing test that fails if the getPCBias(rel.type) is removed but it is in the middle of a larger test that is more difficult to diagnose the problem.

Changes:

  • Clang format run over changed code
  • Improved comment
  • Added test case for specific Arm/Thumb reuse
MaskRay accepted this revision.Mar 1 2021, 1:56 PM
This revision was landed with ongoing or failed builds.Mar 2 2021, 3:06 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptMar 2 2021, 3:06 AM