This is an archive of the discontinued LLVM Phabricator instance.

lld: add experimental support for SHT_RELR sections.
ClosedPublic

Authored by rahulchaudhry on Jun 15 2018, 4:16 PM.

Details

Summary

This change adds experimental support for SHT_RELR sections, proposed
here: https://groups.google.com/forum/#!topic/generic-abi/bX460iggiKg

Pass '--pack-dyn-relocs=relr' to enable generation of SHT_RELR section
and DT_RELR, DT_RELRSZ, and DT_RELRENT dynamic tags.

Definitions for the new ELF section type and dynamic array tags, as well
as the encoding used in the new section are all under discussion and are
subject to change. Use with caution!

Pass '--use-android-relr-tags' with '--pack-dyn-relocs=relr' to use
SHT_ANDROID_RELR section type instead of SHT_RELR, as well as
DT_ANDROID_RELR* dynamic tags instead of DT_RELR*. The generated
section contents are identical.

'--pack-dyn-relocs=android+relr --use-android-relr-tags' enables both
'--pack-dyn-relocs=android' and '--pack-dyn-relocs=relr': lld will
encode the relative relocations in a SHT_ANDROID_RELR section, and pack
the rest of the dynamic relocations in a SHT_ANDROID_REL(A) section.

Diff Detail

Repository
rLLD LLVM Linker

Event Timeline

rahulchaudhry created this revision.Jun 15 2018, 4:16 PM

This patch depends on https://reviews.llvm.org/D47919

I'm still working on adding some unit tests, but I thought I'd send this in for now in case there is any high level feedback on the overall approach.

I've tested this by linking chrome (for amd64 and arm) with '-pie --pack-dyn-relocs=relr'.
For amd64, chrome binary size goes down from 163M to 148M.
For arm, chrome binary size goes down from 101M to 96M.
Installed the generated binaries on both amd64 and arm chromebooks.
The chromebooks boot fine. Played with the browser a little bit. Everything looks ok.
(Support for SHT_RELR is already present in glibc dynamic loader in Chrome OS).

Added tests, ready for review.

mcgrathr added inline comments.Jun 18 2018, 3:29 PM
ELF/Driver.cpp
974

It doesn't seem right to start writing nonzero values into the section data on RELA machines for all relocs.
The addend should only be written in place for words actually converted to RELR slots.

Write addend in section data only for the relocations in .relr.dyn.

rahulchaudhry marked an inline comment as done.Jun 19 2018, 2:15 PM
rahulchaudhry added inline comments.
ELF/Driver.cpp
974

Moved the logic to RelocationBaseSection::addReloc() where Config->WriteAddends is actually checked.

grimar added a subscriber: grimar.Jun 20 2018, 1:25 AM
pcc added inline comments.Jun 22 2018, 3:44 PM
ELF/Config.h
117–118

Can you add an enum class for the --pack-dyn-relocs flag instead of adding these bools?

ELF/SyntheticSections.cpp
1743

Please also include a brief description of the encoding as a comment in the code.

1749

I think you can avoid needing to error on this by only creating RELR relocations for relocations at even offsets in sections with sh_addralign >= 2. In practice I think this would be almost every section that might contain a relative relocation.

1757

Remove unnecessary parens.

1761

Remove unnecessary parens.

1765

Remove unnecessary parens.

ELF/SyntheticSections.h
477

Instead of making this virtual and teaching RelocationBaseSection about RELR I think we should add logic here:
http://llvm-cs.pcc.me.uk/tools/lld/ELF/Relocations.cpp#797
to directly add the relocation to RELR if applicable.

ruiu added a subscriber: ruiu.Jun 24 2018, 10:37 PM
ruiu added inline comments.
ELF/Driver.cpp
882

nit: if you add {} to one of else if, please add it to all if and else ifs.

ELF/SyntheticSections.cpp
1456

I don't get the meaning of this comment. What does if required actually mean? I think that should be answered in the comment. Actually, I'd think instead of writing comment for each expression, you probably should write a function comment to give readers a big picture as to what this function is supposed to do.

1464

Add {}

1719

Please write a function comment so that the first-time reader can understand your code without hassle.

1720

This function seems a bit too long. Please consider splitting this into multiple small functions.

ELF/SyntheticSections.h
522

In lld, we try to keep the class hierarchy as shallow as possible. Please avoid class inheritance when possible.

rahulchaudhry marked 10 inline comments as done.

Relr is now defined directly as packed<uint>.
Added comment describing the SHT_RELR encoding.
Moved the logic for adding a relr relocation to Relocations.cpp.
RelocationBaseSection::addReloc is no longer a virtual function.

ELF/Config.h
117–118

I started on this, but it got clumsy very fast.
The problem is that these bools are not mutually exclusive.
e.g. for --pack-dyn-relocs=android-relr, both RelrPackDynRelocs and AndroidRelrPackDynRelocs are set to true. Most places look at RelrPackDynRelocs, and AndroidRelrPackDynRelocs is only checked to decide which tags to emit. This gets messy when you can only set an enum variable to Relr or AndroidRelr. Many places end up needing to check for both values.
Another example is that --pack-dyn-relocs=android-relr and --pack-dyn-relocs=android are not mutually exclusive. It's fine to have both on the command line, and the effect should be to move relative relocations to SHT_RELR, and pack the remaining relocations in SHT_REL/SHT_RELA using AndroidPackedRelocationSection.

ELF/SyntheticSections.cpp
1464

This logic is now moved to Relocations.cpp

1720

Ack.
The main logic in the function is computing the bitmap, which is 15 lines including comments beginning with 'if ((Base > 0) && (Base <= Current))'
The rest of the function is setting up common types and consts, sorting the offsets, and iterating over them.
I don't see an easy way to split it up without duplicating the common type and const declarations or moving them into the class.

1749

I guess the check would now be in Relocations.cpp before calling InX::RelrDyn->addReloc().
Any hint on what the check would be? I don't see any other obvious place in that file checking for section alignment.
I think this check should still be preserved, just in case something odd ends up here (maybe convert it to fatal?)

ELF/SyntheticSections.h
522

Ack. In this case, the existing hierarchy is

  • RelocationBaseSection inherits from SyntheticSection
  • RelocationSection and AndroidPackedRelocationSection both inherit from RelocationBaseSection

RelrPackedRelocationSection fits right here in the hierarchy with RelocationSection and AndroidPackedRelocationSection as siblings.

pcc added inline comments.Jun 26 2018, 5:11 PM
ELF/Config.h
117–118

for --pack-dyn-relocs=android-relr, both RelrPackDynRelocs and AndroidRelrPackDynRelocs are set to true. Most places look at RelrPackDynRelocs, and AndroidRelrPackDynRelocs is only checked to decide which tags to emit.

I was thinking that you would add a line to the end of this function http://llvm-cs.pcc.me.uk/tools/lld/ELF/Driver.cpp#928 like this:

Config->Relr = Config->PackDynRelocs == Relr || Config->PackDynRelocs == AndroidRelr;

then have the code check Config->Relr in most places.

Another example is that --pack-dyn-relocs=android-relr and --pack-dyn-relocs=android are not mutually exclusive. It's fine to have both on the command line, and the effect should be to move relative relocations to SHT_RELR, and pack the remaining relocations in SHT_REL/SHT_RELA using AndroidPackedRelocationSection.

That doesn't look like the current behaviour though?

That said, can we just make --pack-dyn-relocs=android-relr mean "use SHT_ANDROID_RELR and SHT_ANDROID_REL/SHT_ANDROID_RELA"? Is there any case in which it would be useful to have SHT_ANDROID_RELR combined with unpacked SHT_REL/SHT_RELA?

ELF/Relocations.cpp
825

Re SyntheticSections.cpp:1752 comment I think this can be something like if (InX::RelrDyn && Sec.Alignment >= 2 && Offset % 2 == 0) now.

ELF/SyntheticSections.cpp
1456–1457

I don't think you need to add logic here at all. Instead, you can add the static relocation directly to the input section in Relocations.cpp when you decide to add the relocation to RELR.

ELF/SyntheticSections.h
522

It doesn't really fit though because RelrPackedRelocationSection is unlike the other sections in that it can only store one specific type of relocation. With the change to add relocations directly to InX::RelrDyn I think you can just make this class derive from SyntheticSection and have it store a vector of (section, offset) pairs instead of DynamicRelocs.

pcc added inline comments.Jun 26 2018, 5:19 PM
ELF/SyntheticSections.cpp
1749

I think this check should still be preserved, just in case something odd ends up here (maybe convert it to fatal?)

We shouldn't expect this to happen because of the guarantees provided by the rest of the program, so you can make it an assert.

ruiu added inline comments.Jun 26 2018, 9:45 PM
ELF/SyntheticSections.cpp
1758

This is the same as Config->Wordsize.

1765

I think you can always use std::vector<uint64_t> instead of defining Word and using std::vector<Word> because the larger integral type will just work fine for 32-bit machines in this case.

1775

Could you use clang-format-diff to format your patch?

1782

I believe you can use uint64_t as well. We generally prefer uint64_t instead of the target-dependent integral type for the sake of simplicity.

Added an enum class for the --pack-dyn-relocs flag.
Added another option "android+relr" that implies both "android" and "android-relr" packing.
Another place in Relocations.cpp needed change to add relative relocations in RelrDyn instead of RelaDyn.
Relocations are only added to RelrDyn if "Sec.Alignment >= 2 && Offset % 2 == 0".

rahulchaudhry marked 7 inline comments as done.Jun 28 2018, 4:48 PM
rahulchaudhry added inline comments.
ELF/Config.h
117–118

I think it would be better to keep the two packing modes independent:

  • For debugging, someone might want to enable SHT_ANDROID_RELR but not SHT_ANDROID_RELA, or vice-versa.
  • At some later date, Android might decide to remove support for the custom (non-standard) SHT_ANDROID_RELA packing. This becomes cumbersome if SHT_ANDROID_RELR implies SHT_ANDROID_RELA.

I added another recognized form for this option: "android+relr", which is a combination of "android" and "android-relr".
The naming is a bit confusing now. The "+" means plus/addition, but the "-" means hyphen (not minus/subtraction).
Maybe "android-relr" should be renamed to "androidrelr" without the hyphen?

Also added an enum class, but that did not improve things much.
The three bools are still there, but now they're set in Driver.cpp:setConfigs() using the enum value in Config->PackDynRelocs.

ELF/Relocations.cpp
776

After logic to add relocations to RelrDyn was moved to Relocations.cpp, I noticed that chrome binary still had ~20,000 relative relocations left over in RelaDyn.
This is the place where those remaining relocations were coming from.
So moving this logic to the callers of addReloc() (instead of making addReloc virtual) does result in duplicating this logic.

There are a few other places that add RelativeRel to RelaDyn, but they're MipsGotSection::build(), so I assume they're mips specific.
I have not put the logic there yet, so those relocations may still end up in RelaDyn instead of RelrDyn.

ELF/SyntheticSections.cpp
1456–1457

There are at least two places where RelSec is set to either RelaDyn or RelrDyn. This logic for writing the addends would need to be in both places. There might be more places in the future, and it becomes all too easy (i.e. errorprone) to add a relocation to RelrDyn, but forget to write the addend for it in the section.
I think keeping this logic in one place is desirable.

ELF/SyntheticSections.h
522

Deriving RelrPackedRelocationSection directly from SyntheticSection has several consequence:

  • It cannot use the addReloc() functions from RelocationBaseSection. It'd need its own addReloc() and a vector of (section, offset) pairs like you suggested. This affects all call sites that do RelSec->addReloc(). Currently RelSec can be InX::RelaDyn or InX::RelrDyn and the same addReloc() call works fine for both. I think there's some value to storing DynamicRelocs the same way for all types of relocation sections.
  • RelrPackedRelocationSection needs to be a template on <class ELFT> (similar to RelocationSection and AndroidPackedRelocationSection). RelocationBaseSection is not templated, and as such, RelaDyn, RelaPlt, etc are all declared as RelocationBaseSection* in struct InX. Currently RelrDyn is also in struct InX as RelocationBaseSection*. If it inherits directly from SyntheticSection, it would need to be moved to struct In<ELFT>. This would mean all references to InX::RelrDyn would have to converted to In<ELFT>::RelrDyn. All this makes using or referencing RelrDyn very unlike using or referencing RelaDyn when it is conceptually very similar.
  • On top of the above, there are at least some places where InX::RelrDyn is referenced, but class ELFT is not available. Converting to In<ELFT>::RelrDyn would mean turning those functions into template versions with <class ELFT> as well. This can have a cascading effect, reversing some of the detemplating effort that I see has taken place in recent past.

I am not convinced that RelrPackedRelocationSection is so unlike the other classes for relocation sections that it doesn't fit in the heirarchy here and it's worth going through all this trouble to avoid inheriting from RelocationBaseSection.

pcc added inline comments.Jun 28 2018, 6:34 PM
ELF/Config.h
117–118

Seems reasonable enough, and if we're going to go that way I think I'm convinced that you don't need the enum class.

I think you can avoid needing to have both android-relr and android+relr by having the flags look like this:

  • --pack-dyn-relocs=android -- use Android packing
  • --pack-dyn-relocs=relr -- use RELR packing
  • --pack-dyn-relocs=android+relr -- do both of the above
  • --use-android-relr-tags -- use SHT_ANDROID_RELR tag instead of SHT_RELR
ELF/Relocations.cpp
776

You could always add a function addRelativeReloc and call it from both places as well as the places in the MIPS code.

ELF/SyntheticSections.cpp
1456–1457

There are at least two places where RelSec is set to either RelaDyn or RelrDyn.

Those places become a single place if you introduce addRelativeReloc. If for whatever reason new code ends up calling InX::RelaDyn->addReloc (although I don't see why since the author of that code would probably follow existing code that calls addRelativeReloc), that wouldn't be an error, it would just mean that that relocation wouldn't be compressed.

ELF/SyntheticSections.h
522

This affects all call sites that do RelSec->addReloc()

Only the one in addRelativeReloc.

RelrPackedRelocationSection needs to be a template on <class ELFT> (similar to RelocationSection and AndroidPackedRelocationSection).

Yes, that's annoying. You can solve it in the same way as we avoid templating RelocationBaseSection on ELFT: introduce a RelrBaseSection which stores the (section, offset) pairs and derive RelrSection<ELFT> from it.

I am not convinced that RelrPackedRelocationSection is so unlike the other classes for relocation sections that it doesn't fit in the heirarchy

From my perspective it's not so much a matter of fitting in a hierarchy but using appropriate data structures. There's no need to use a data structure for arbitrary dynamic relocations when a simpler one would suffice.

test/ELF/pack-dyn-relocs.s
1

Please add a test showing that misaligned relative relocations end up in .rel.dyn or .rela.dyn.

I'm a little concerned that the only test for this is aarch64/arm specific, and won't run on hosts with only x86 enabled. We tend to use x86/x86_64 for generic testing, from what I understand.

I'm not actually sure what the solution is though, since it doesn't make sense to duplicate the test logic really, and some of the test is android (so arm, if I'm not mistaken) specific.

Reverted the enum class for --pack-dyn-relocs.
Added class RelativeReloc that is similar to DynamicReloc but only stores relative relocations.
Added class RelrBaseSection that is similar to RelocationBaseSection but stores RelativeRelocs instead of DynamicRelocs.
RelrPackedRelocationSection now inherits from RelrBaseSection.
Updated test to add a relative relocation with odd offset.

rahulchaudhry marked 5 inline comments as done.Jun 29 2018, 2:59 PM
rahulchaudhry added inline comments.
ELF/Config.h
117–118

Added new flag --use-android-relr-tags.

ELF/SyntheticSections.h
522

Ah.. I see. So a little bit of code duplication is okay in the interest of keeping the class hierarchy more flat.
I added RelrBaseSection, which stores std::vector<RelativeReloc>.
RelativeReloc is similar to DynamicReloc, but only stores Section and Offset.

pcc added a comment.Jun 29 2018, 4:17 PM

Thanks, this is closer to what I had in mind. But I was imagining that addRelativeReloc would be a free function so that you can move the rest of the logic into it. I wrote a patch on top of yours with what I had in mind and attached it to the review. I also made a number of smaller changes as well.

ELF/Driver.cpp
885

I was imagining that --use-android-relr-tags would be orthogonal to --pack-dyn-relocs=android+relr, so that you get the standard relr tags unless the user specifically asks otherwise.

886–889

You don't need this part because the flags are initialized to false.

ELF/SyntheticSections.cpp
1502

As the comment says there is no need for a link if all relocations are relative. In my patch I just removed this function.

rahulchaudhry marked 2 inline comments as done.

Applied patch from pcc and made --use-android-relr-tags independent of --pack-dyn-relocs.

rahulchaudhry marked 2 inline comments as done.Jun 29 2018, 4:46 PM

Thanks for the patch. Things look much cleaner now.

pcc added a comment.Jun 29 2018, 6:00 PM

Looks great. Rui, what do you think?

ruiu added a comment.Jul 1 2018, 11:59 PM

Overall looking good.

ELF/Driver.cpp
889–890

Move this before the code to initialize Config->UnresolvedSymbols.

ELF/Relocations.cpp
720

This function needs comment. (Any non-trivial code needs comment so that the code can be understood by first-time readers.)

ELF/SyntheticSections.cpp
1711

Elf_Relr -> Config->Wordsize

1761

This loop looks odd to me because it doesn't reflect the logic that this loop should implement. Currently, the loop looks like this

while () {
   do_something();
   if (...)
    add_a_leading_address_entry();
   else
    add_a_bitmap();
}

However, IIUC, the straightforward translation of the logic in the pseudo code should look like this:

while (there's remaining relocation) {
  add_a_first_address(the first remaining relocation);
  while (more relocations can be folded)
    add_a_bitmap(foldable relocations);
}

As a result, I think you had to write non-obvious code to determine whether you need to add a leading address entry or a bitmap. I believe this code can be (and perhaps should be) improved. That said, I'm fine if you submit this code as-is. I'll try to address that as a follow-up patch.

1783

Please use typename ELFT::uint instead of Elf_Relr.

ELF/SyntheticSections.h
534

Please write a comment as to what this class represents.

547

Use typename ELFT::uint instead of ELF_Relr.

rahulchaudhry marked 4 inline comments as done.

Added some comments, plus some minor edits.

ELF/SyntheticSections.cpp
1783

See above.

ELF/SyntheticSections.h
547

I don't think these are interchangeable here. Elf_Relr is defined as packed<uint> in ELFT. The packed<> takes care of endianness conversion when cross-compiling for a target architecture with a different endianness.
RelrRelocs is written to output using a memcpy() in writeTo(). If we convert RelrRelocs to store raw ELFT::uint values, we'll need to do byte swapping in writeTo() in case the target endianness is different.
Maybe I'm missing something or understood it all wrong.

rahulchaudhry edited the summary of this revision. (Show Details)Jul 2 2018, 12:59 PM

Some updates from the testing front:

I took the latest version of this patch and used it to link Chrome for Chrome OS (with '--pack-dyn-relocs=relr', for both amd64 and arm).
Flashed the newly built chrome binaries onto two chromebooks.
They boot fine. Everything seems to be working.

Also used this patch to do a full Android build for Pixel XL (with '--pack-dyn-relocs=android+relr --use-android-relr-tags').
Flashed the image to a test device.
It boots fine. Everything seems to be working.
Here's the CL for some size comparison numbers between different --pack-dyn-relocs options: https://android-review.googlesource.com/709131

pcc added inline comments.Jul 3 2018, 2:09 PM
ELF/SyntheticSections.cpp
1783

I guess uint would work here because the value is only stored temporarily in R.

That said, it looks like you could simplify the code a little by changing the code in the two branches to push values onto RelrRelocs directly instead of storing them in R.

rahulchaudhry added inline comments.Jul 3 2018, 2:24 PM
ELF/SyntheticSections.cpp
1783

The assignment to R is doing an implicit conversion from uint to packed<uint>.
If I try to do RelrRelocs.push_back(Current), build fails with "no matching function for call to ...".
We'll need explicit conversion, i.e.

RelrRelocs.push_back(Elf_Relr(Current));

and

RelrRelocs.push_back(Elf_Relr((Bits << 1) | 1));

It makes the conversion explicit (maybe that's better), and it has to be done at two places.

Alternately, I can make RelrRelocs a vector<uint> as Rui suggested, then modify writeTo to iterate over entries and convert each before writing instead of using a single memcpy to write all of them.

pcc added inline comments.Jul 3 2018, 2:33 PM
ELF/SyntheticSections.cpp
1783

I think that making the conversion explicit here is fine and probably a little clearer too, so that's what I'd go with.

rahulchaudhry edited the summary of this revision. (Show Details)

Made the conversion to Elf_Relr explicit.

rahulchaudhry marked an inline comment as done.Jul 3 2018, 3:01 PM
ruiu accepted this revision.Jul 5 2018, 11:23 AM

LGTM

ELF/Relocations.cpp
722–728

Well, this comment explains what you are doing in this function, but that's what I can find by reading this function, so I don't find this very helpful. I'd explain the intention instead. For example, this comment should answer to the question why the offset must be aligned to 2, what is RelrDyn in the first place, etc.

Now that I understood the entire patch, I'll rewrite this patch after you commit this change so that we can proceed, though.

This revision is now accepted and ready to land.Jul 5 2018, 11:23 AM
rahulchaudhry added inline comments.Jul 6 2018, 10:45 AM
ELF/Relocations.cpp
722–728

I cannot commit this change as I do not have write access.
I won't ask you to commit it either, since it is clear that you are not happy with this change.
You've indicated a couple of times that you would like to rewrite this patch.
I would suggest that you re-implement the functionality to your liking, and simply commit that instead.
Unfortunately, I will not be able to spend any more time on this.
Thanks for your time,
Rahul

This revision was automatically updated to reflect the committed changes.